Erdős Problem #123
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problems openaigpt 6 astra ultragpt pro 5.2 100% cataloguedSolvedSolvedStatement
Fix integers $a,b,c\ge 2$ with $\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1$. Let \[ S(a,b,c)\;:=\;\{a^k b^\ell c^m : k,\ell,m\in \mathbb{N}_0\}\subset \mathbb{N}. \] (So $1\in S$.)
A finite subset $T\subset S$ is called divisibility-antichain if for any two distinct $x,y\in T$ neither $x\mid y$ nor $y\mid x$.
Call $S$ $d$-complete if there exists $N_0$ such that every integer $n\ge N_0$ can be written as \[ n = \sum_{t=1}^M s_t \] for some finite divisibility-antichain $\{s_1,\dots,s_M\}\subset S$ (in particular all $s_t$ are distinct).
Problem. Determine for which pairwise coprime triples $(a,b,c)$ the set $S(a,b,c)$ is $d$-complete.
Stress points / edge cases to watch: - The antichain condition forbids using both $1$ and any other element (since $1$ divides everything). - Divisibility structure depends strongly on prime factorizations; pairwise coprime assumption is crucial.
Restatement from Math-5443-A2 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 2
GPT 6 Astra Ultra attempt on Math-5443
FORMAL RESTATEMENT
Erdős #123; reconstruction, 2026-09-23. Let $a,b,c>1$ be pairwise coprime. Must every sufficiently large integer be a sum of distinct numbers $a^ib^jc^k$, with nonnegative exponents, such that no selected number divides another?QUICK LITERATURE AND CONTEXT CHECK
The current page records a recent affirmative resolution. We reconstruct the level-set argument in the primary exposition hosted by Thomas Bloom, expanding its residue-correction and interval steps. Van der Waerden's theorem is an external classical input. This is an exposition of that known proof, not a new solution or a report of running its formalization.WORK
Relabel the bases so that $a<c<b$, and write $L_D=\{a^ib^jc^k:i+j+k=D\}$. Pairwise coprimality implies divisibility is coordinatewise in $(i,j,k)$; thus every subset of one $L_D$ is an antichain for divisibility. We seek long intervals of subset sums on one level.Progressions with a bounded $b$ exponent
Put $\phi=\varphi(c)$ and $H=\phi(c-2)$. For $E\ge H$ and $0\le r<c$, take \[ P_E(r)=\{a^{E-H+\phi t}b^{\phi(c-2-t)}:0\le t<r\}\subseteq L_E. \] Its sum is $r a^{E-H}$ modulo $c$, by Euler's theorem. Given a word $(r_0,\ldots,r_{h-1})\in\{0,\ldots,c-1\}^h$, form \[ F=\bigcup_{i=0}^{h-1}c^iP_{H+h-1-i}(r_i)\subseteq L_{H+h-1}. \] These unions have no repeated terms since their $c$ exponents differ. If two words first differ at index $i$, the difference of their sums has $c$-adic order exactly $i$: after division by $c^i$, the difference is $(r_i-r_i')a^{h-1-i}$ modulo $c$, which is nonzero. Hence the sums represent all residues modulo $c^h$, exactly once. All $b$ exponents are at most $H$. Since $a<c$, summing the resulting geometric series bounds every sum by $Kc^h$, with $K$ independent of $h$. Color each residue in $[0,c^h)$ by the quotient of its sum by $c^h$. The number of colors is bounded. Van der Waerden's theorem therefore gives, for any prescribed $L>1$, sets $E_0,\ldots,E_{L-1}\subseteq L_\delta$ whose sums are $s,s+d,\ldots,s+(L-1)d$ with $d>0$, and whose $b$ exponents are at most $H$.Two auxiliary interval and residue facts
For coprime integers $1<A<B$, put $L=4AB$. The digit sums \[ T_N=\left\{\sum_{e=0}^N r_e A^{N-e}B^e:0\le r_e<L\right\} \] contain integer intervals $[U_N,V_N]$ satisfying \[ V_N-U_N\ge2AB^{N+1},\qquad 0\le U_N\le V_N\le K_1B^{N+1}. \tag{1} \] For completeness start with $U_0=0,V_0=L-1$. Given an interval at stage $N-1$, use $T_N=AT_{N-1}+\{0,\ldots,L-1\}B^N$. For each residue modulo $A$, the allowed digits form a progression of step $A$. Their translated intervals overlap in that residue, since $V_{N-1}-U_{N-1}\ge B^N-1$. All residues therefore fill the interval with endpoints \[ U_N=AU_{N-1}+(A-1)B^N,\quad V_N=AV_{N-1}+(L-A)B^N. \] Its width is at least $2A^2B^N+(4AB-2A+1)B^N\ge2AB^{N+1}$. The endpoint upper bound follows by summing a geometric series with ratio $A/B<1$.Fix a modulus $\Delta$. For all large $D$, every residue modulo $\Delta$ is a subset sum of face monomials in $L_D$, of total size at most $K_2c^D$. Here a face means that at least one exponent is zero. To verify this sometimes useful detail, choose a common eventual period $T$ and threshold for the three sequences $a^j,b^j,c^j$ modulo $\Delta$. Choose a fixed $R$ larger than that threshold plus $\Delta T$. For large $D$, the three numbers \[ b^Rc^{D-R},\quad a^Rc^{D-R},\quad a^{D-R}b^R \] have collective gcd $1$, so their residues generate $\mathbb Z/\Delta$. Any desired residue is a combination with coefficients in $\{0,\ldots,\Delta-1\}$. Replace a coefficient by that many distinct copies obtained by moving $0,T,2T,\ldots$ units of exponent along the same face. Eventual periodicity preserves every residue. The three families lie in different face interiors and so are disjoint. Their $b$ exponents are bounded independently of $D$, and $a<c$, proving the claimed $K_2c^D$ sum bound.
Amplification to every large integer
Choose $u>H+1$ and then $v\ge2$ so large that $ba^v<c^v$. Set \[ A=a^{u+v},\quad B=b^uc^v,\quad q=abc, \] so $A<B$ and $(A,B)=1$. Obtain the progression of sets $E_r$ above with length $L=4AB$, and put $\Delta=qd$. At stage $N$, multiply $E_{r_e}$ by $qA^{N-e}B^e$ for $0\le e\le N$ and take their union. All terms lie in \[ L_{D_N},\qquad D_N=\delta+(u+v)N+3. \] Their $b$ exponents lie in the disjoint ranges $[ue+1,ue+H+1]$, so there are no repeated terms. Their sums range over \[ O_N+\Delta T_N,\qquad O_N=qs\sum_{e=0}^NA^{N-e}B^e. \] Every such term lies in the interior of the exponent simplex. We can therefore adjoin the face corrections without collisions. By $1$, all integers in \[ J_N=[\lceil O_N+\Delta U_N+K_2c^{D_N}\rceil, O_N+\Delta V_N] \] are represented: choose a face correction of the needed residue modulo $\Delta$ and subtract it. Since $c^{D_N}/B^N=c^{\delta+3}(c/b)^{uN}\to0$, the interval $J_N$ has length at least $X=qB^N$ for large $N$, and its lower endpoint is at most $KB^{N+1}$ for a fixed $K$.For each $H+2\le s\le N$, consider the interior monomials with $b$ exponent $uN+s+1$. Along this line successive values have ratio $c/a$. The smallest value, with $c$ exponent $1$, divided by $X$ is \[ a^{\delta-s}(ba^v/c^v)^N b^{s-N}\le a^\delta(ba^v/c^v)^N\longrightarrow0. \] Equivalently its exact ratio is $a^{\delta-s}b^s(a/c)^{vN}$; the displayed bound uses $s\le N$ and $a^{-s}\le1$. The largest value, with $a$ exponent $1$, has ratio $c^\delta(b/c)^s>1$. The line therefore contains a term $z_s$ with $(a/c)X<z_s\le X$. These terms are distinct, lie above every earlier block in $b$ exponent, and lie off the faces. They may be adjoined independently. Adding a new available summand no larger than the length of an interval of represented integers extends that interval by the summand. Thus we obtain an interval $I_N$ of subset sums on $L_{D_N}$ with \[ \inf I_N\le KB^{N+1},\qquad |I_N|-1\ge\kappa N B^N \] for fixed $\kappa>0$ and large $N$. Choose an integer $t$ such that $KB^{1-t}\le1$. For large $M$ take $N=M-t$. Then the lower endpoint is at most $B^M$, while the interval length is at least $B^{M+1}$. Hence $[B^M,B^{M+1})\subseteq I_N$. These intervals cover every sufficiently large integer. Each representation belongs to one level and is therefore primitive. $\square$
VERIFICATION
Distinctness is enforced in three separate places: the initial words use distinct $c$ exponents; amplified blocks use disjoint $b$ ranges; face corrections and final extension terms occupy disjoint regions. Pairwise coprimality is essential for coordinatewise divisibility and the residue corrections. A mere collective gcd of $1$ does not suffice. Finite tests of the digit intervals and primitive levels accompany this batch, but do not replace the asymptotic construction.FINAL STATUS
SOLVED (known affirmative proof reconstructed). The only substantial general theorem used without proof is van der Waerden's finite coloring theorem. The auxiliary radix and face-residue arguments are expanded above. No new result is claimed.SOURCES
https://www.erdosproblems.com/123. Primitive Representations by Three Coprime Bases, primary exposition linked from the current problem page, https://www.thomasbloom.org/erdos123.pdf. Checked 2026-09-23. Completion is relative to the stated classical input.COMPLETION ESTIMATE
COMPLETION: 100%gpt pro 5.2 attempt on Math-5443
1) FORMAL RESTATEMENT
Fix integers $a,b,c\ge 2$ with $\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1$. Let \[ S(a,b,c)\;:=\;\{a^k b^\ell c^m : k,\ell,m\in \mathbb{N}_0\}\subset \mathbb{N}. \] (So $1\in S$.)
A finite subset $T\subset S$ is called divisibility-antichain if for any two distinct $x,y\in T$ neither $x\mid y$ nor $y\mid x$.
Call $S$ $d$-complete if there exists $N_0$ such that every integer $n\ge N_0$ can be written as \[ n = \sum_{t=1}^M s_t \] for some finite divisibility-antichain $\{s_1,\dots,s_M\}\subset S$ (in particular all $s_t$ are distinct).
Problem. Determine for which pairwise coprime triples $(a,b,c)$ the set $S(a,b,c)$ is $d$-complete.
Stress points / edge cases to watch: - The antichain condition forbids using both $1$ and any other element (since $1$ divides everything). - Divisibility structure depends strongly on prime factorizations; pairwise coprime assumption is crucial.
2) QUICK LITERATURE/CONTEXT CHECK
(Restricted to statements explicitly present in 123-137.tex.) - Erdos and Lewin $1981$ proved $S(a,b,c)$ is $d$-complete for $(a,b,c)=(3,5,7)$. - For $(a,b,c)=(2,5,c)$ with $c$ odd and $c\not\equiv 1\pmod 4$, the sequence is $d$-complete (quoted as due to Erdos and Szekeres, 1960). - Ma and Chen $1990$ proved $d$-completeness for $(a,b,c)=(2,3,5)$. - Erdos conjectured a stronger form for $(2,3,5)$: for every $\varepsilon>0$, all large integers can be represented as a sum of distinct non-dividing elements of $\{2^k3^\ell5^m\}$, all lying in $[b_1,(1+\varepsilon)b_1)$.
3) ATTACK PLAN
- Translate divisibility into a partial order on exponent vectors $(k,\ell,m)$. - Try to understand antichains in that poset and whether their value-sums can cover long intervals. - Do small computational searches for representability thresholds for specific triples (sanity checks).
4) WORK
Lemma 4.1 (Coordinatewise divisibility). Let $(a,b,c)$ be pairwise coprime and let $x=a^k b^\ell c^m$ and $y=a^{k'} b^{\ell'} c^{m'}$. Then \[ x\mid y \quad\Longleftrightarrow\quad k\le k',\ \ell\le \ell',\ m\le m'. \]
Proof. Because $a,b,c$ are pairwise coprime, every prime factor of $a$ is coprime to $b$ and $c$, etc. Thus in the prime factorization of $x$ the primes coming from $a$ occur to exponents proportional to $k$, those from $b$ proportional to $\ell$, and those from $c$ proportional to $m$, and these groups of primes are disjoint. Therefore $x\mid y$ holds exactly when the $a$-part of $x$ divides the $a$-part of $y$ (i.e. $k\le k'$), and similarly for the $b$- and $c$-parts. $\square$
Lemma 4.2 (Antichains are antichains of exponent vectors). A finite set $T\subset S(a,b,c)$ is a divisibility-antichain if and only if the corresponding set of exponent vectors \[\{(k,\ell,m): a^k b^\ell c^m\in T\}\subset \mathbb{N}_0^3\] is an antichain under the product order $\preceq$ defined by $(k,\ell,m)\preceq (k',\ell',m')$ iff $k\le k'$, $\ell\le \ell'$, $m\le m'$.
Proof. Immediate from Lemma 4.1. $\square$
FAST REALITY CHECK (computation). For each triple, I generated all monomials $a^k b^\ell c^m\le X$ and searched (by backtracking) for representations of each $n\le X$ as a sum of distinct monomials with the antichain condition. Results: - For $(a,b,c)=(2,3,5)$: every integer $1\le n\le 1000$ is representable. - For $(a,b,c)=(3,5,7)$: among $1\le n\le 1000$ exactly the following $19$ integers are not representable: \[ \{2,4,6,11,13,17,18,19,20,23,29,33,37,43,51,92,100,148,185\}. \] In particular, all integers $186\le n\le 1000$ are representable in this sense.
5) VERIFICATION
- Lemma 4.1 uses only disjointness of prime factors of $a,b,c$; pairwise coprime is exactly what is needed. - Lemma 4.2 is a direct reformulation. - The computation only uses summands $\le X$, which is valid because all summands are positive; any representation of $n\le X$ uses summands $\le n\le X$.
6) FINAL
UNRESOLVED
(i) Strongest fully proved partial result: - The divisibility relation in $S(a,b,c)$ is exactly coordinatewise on exponent vectors (Lemma 4.1), so the antichain condition is an antichain condition in $\mathbb{N}_0^3$ (Lemma 4.2). - Computational evidence: $(2,3,5)$ represents all $n\le 1000$; $(3,5,7)$ represents all $186\le n\le 1000$.
(ii) Exact first gap: - Prove (or disprove) that for every pairwise coprime triple $(a,b,c)$, the set $S(a,b,c)$ is $d$-complete (or classify precisely which triples are).
(iii) Top 3 next moves: 1. Try to build a greedy / covering argument on the exponent-poset antichains that yields long intervals of attainable sums. 2. Attempt a minimal-counterexample analysis: if a large $n$ is not representable, constrain the maximal element in any candidate antichain and derive contradictions. 3. Search for structured counterexamples where antichains are forced to be too sparse (e.g., when one base is a large prime vs a small base) and test computationally for growing gaps.
(iv) What a minimal counterexample would likely look like: - A triple where one base is so small that divisibility-comparabilities force antichains to concentrate on a narrow "layer" of exponent vectors, potentially limiting attainable sums; or conversely where one base is huge so available summands are too lacunary.