Erdős Problem #283

Erdős Problem #283

Statement and attribution

Let $p$ be a polynomial taking integer values on $\mathbb Z$, with positive leading coefficient and no fixed divisor greater than one. Must every sufficiently large integer $m$ have a representation \[ \sum_{n\in A}\frac1n=1,\qquad \sum_{n\in A}p(n)=m \] with $A$ a finite set of distinct positive integers? Yes. We reconstruct the switching proof credited to GPT-5.5 Pro, prompted by Price and edited by Barreto, using the formalization-informed presentation linked in the current discussion. The proof works with any prescribed rational reciprocal sum $\alpha>0$ and any lower bound on the denominators. No novelty is claimed.

The substantial external input is the Roth--Szekeres--Graham completeness theorem: a nonconstant rational polynomial $q$ taking positive integer values on the positive integers, with positive leading coefficient and gcd of its values equal to one, has every sufficiently large integer as a finite sum of values $q(j)$ with distinct indices. We use this theorem explicitly; its proof is not reproduced. Integer-valued polynomials on $\mathbb Z$ have rational coefficients by interpolation.

Work I: elementary tools and residue corrections

First, every rational $R>0$ is a sum of reciprocals of distinct integers exceeding any prescribed bound $L$. Take the longest initial segment $L+1,\ldots,N$ whose reciprocal sum is strictly below $R$; its remaining rational residual is at most $1/(N+1)$. The usual greedy Egyptian algorithm terminates: for a residual $a/b$ in lowest terms and $q=\lceil b/a\rceil$, the positive new numerator $aq-b$ is smaller than $a$, unless the residual is already $1/q$. Its denominators strictly increase and start at least at $N+1$. Increasing $L$ to at least one ensures every denominator is at least two. Moreover splitting the largest denominator $y$ by \[ \frac1y=\frac1{y+1}+\frac1{y(y+1)} \tag{1} \] preserves distinctness and increases the number of terms by one. Thus all sufficiently large numbers of terms occur.

Call a finite set $E\subseteq\{2,3,\ldots\}$ a pattern if $\sum_{e\in E}1/e=1$, and put $Q_E(x)=\sum_{e\in E}p(ex)-p(x)$. For any positive integers $T,H$ and residue $b\pmod H$, there is a pattern all of whose elements are divisible by $T$ and with $|E|\equiv b\pmod H$: represent the rational number $T$ by sufficiently many distinct reciprocal terms and multiply all their denominators by $T$. The preceding length adjustment gives the prescribed cardinality; if $T=1$, use denominators exceeding one.

Suppose $p$ has degree $r\ge1$ and leading coefficient $a>0$. Every $Q_E$ has degree $r$ and positive leading coefficient $a(\sum_{e\in E}e^r-1)$. We claim \[ \gcd\{Q_E(n):E\hbox{ a pattern},\ n\ge1\}=1. \tag{2} \] Choose $B\ge1$ with $Bp\in\mathbb Z[x]$. Modulo an integer $h$, the values of $p$ have period $hB$: polynomial differences for $Bp$ are divisible by $hB$, and division by $B$ gives the assertion. If a prime $\ell$ divided every value in $2$, choose a pattern whose elements are divisible by $\ell B$ and whose cardinality is divisible by $\ell$. Then $Q_E(n)\equiv|E|p(0)-p(n)\equiv-p(n)\pmod\ell$, contradicting the absence of a fixed prime divisor for $p$. This proves $2$. Finitely many of these switching values already have gcd one, so finitely many patterns suffice.

Work II: a long family of independent switches

Fix a rational $\alpha>0$ and a denominator bound $L$. Put \[ P=36,\quad u_j=Pj+1,\quad D_j=u_ju_{j+1},\quad A(x)=p(2x)+p(3x)+p(6x)-p(x). \] Write $\Theta=2^r+3^r+6^r-1>1$ and $\lambda=aP^{2r}$. Choose $J$ large enough that all $A(D_j)>0$ for $j\ge J$, all relevant initial denominators exceed $L$, and $1/(Pu_J)<\alpha$. Let \[ g=\gcd_{j\ge J}A(D_j),\qquad \mu=\lambda(1+\Theta)/2. \] The polynomial whose values are $A(D_j)/g$, reindexed from $j=J$, satisfies the completeness theorem. In particular there is $M_0$ such that, for all large $N$, every multiple $M$ of $g$ in \[ M_0\le M\le\mu N^{2r} \tag{3} \] is a sum of distinct values $A(D_j)$ with $J\le j\le N$. To verify the finite upper limit, the theorem first provides a representation using arbitrary $j\ge J$. But $A(D_j)\sim\lambda\Theta j^{2r}$ and $\mu<\lambda\Theta$, so every term with $j>N$ exceeds $\mu N^{2r}$ for large $N$. Positivity excludes such terms from a representation in $3$. The rational polynomial $A(D_j)/g$ is integer-valued on every positive integer of its reindexing, which also implies integer-valuedness on all integers: clear its coefficient denominators and move an argument to a positive one in the same residue class modulo that denominator.

We need only finitely many additional switches to correct residues modulo $g$. By $2$, choose switching values $Q_{E_\sigma}(b_\sigma)$ whose residues generate $\mathbb Z/g\mathbb Z$. Make $g-1$ separate copies of each type. For each copy choose a large integer $c_\nu\equiv b_\sigma\pmod{gB}$, with pattern $G_\nu=E_\sigma$, so that \[ b_\nu:=Q_{G_\nu}(c_\nu)>0, \qquad C_0:=\sum_\nu1/c_\nu<\alpha-1/(Pu_J). \tag{4} \] Also require every candidate denominator $ec_\nu$, $e\in\{1\}\cup G_\nu$, to avoid all other copies' candidates and every $hD_j$ with $h\in\{1,2,3,6\}$ and $j\ge J$.

These choices exist: in a fixed residue class the available integers $c\le X$ number $X/(gB)+O(1)$, whereas each collision equation $ec=hD_j$ excludes only $O(\sqrt X)$ choices, since $D_j\asymp j^2$. There are finitely many multiplier pairs and finitely many previously chosen candidates. Arbitrarily large choices remain, giving positivity and $4$ as well. The residues of subset sums of the $b_\nu$ fill every class modulo $g$: express a residue as an integer combination of the generators and reduce each coefficient to $0,\ldots,g-1$. Let $B_*:=\sum_\nu b_\nu$. When $g=1$ use no correction copies and put $C_0=B_*=0$.

Work III: fill the reciprocal sum and prevent collisions

Set $R_0=\alpha-1/(Pu_J)-C_0>0$. Let $Y$ exceed all correction candidates and $L$, and choose an integer $\Lambda>Y$ divisible by eight. Represent $\Lambda R_0$ as a finite sum of distinct unit fractions $\sum_{f\in F}1/f$. The fixed denominators $\Lambda f$ then have reciprocal sum $R_0$. For $N\ge J$, put $\tau_N=Pu_{N+1}$. Telescoping gives \[ \sum_{j=J}^{N}\frac1{D_j}+\frac1{\tau_N}=\frac1{Pu_J}. \tag{5} \] Together with the correction denominators $c_\nu$ and the fixed denominators $\Lambda f$, this is a representation of $\alpha$.

Independently switch any chosen $D_j$ to $2D_j,3D_j,6D_j$, and any chosen $c_\nu$ to the set $\{ec_\nu:e\in G_\nu\}$. Each operation preserves the reciprocal sum and adds respectively $A(D_j)$ or $b_\nu$ to the polynomial sum.

We verify distinctness for every selection. Since $u_j\equiv1\pmod{36}$, the candidates $hD_j$ have four different valuation pairs $(v_2,v_3)$, namely $(0,0),(1,0),(0,1),(1,1)$ for $h=1,2,3,6$. Equal candidates must therefore have the same $h$, and then strict increase of $D_j$ gives the same $j$. The denominator $\tau_N$ has valuation pair $(2,2)$, so never meets them. Fixed denominators have $v_2\ge3$, and are larger than all correction candidates. Correction candidates were chosen to avoid each other and all main candidates. Finally $\tau_N>Y$ for large $N$, excluding the remaining possible collisions. All denominators exceed $L$.

Work IV: every sufficiently large integer occurs

Let the unswitched polynomial sum be \[ B_N=\sum_{j=J}^{N}p(D_j)+p(\tau_N) +\sum_\nu p(c_\nu)+\sum_{f\in F}p(\Lambda f). \] For each sufficiently large $N$, every integer in \[ [B_N+B_*+M_0,\ B_N+\mu N^{2r}] \tag{6} \] is attainable. Indeed choose a correction subset with sum $\Delta\equiv m-B_N\pmod g$. Since $0\le\Delta\le B_*$, the residual $M=m-B_N-\Delta$ satisfies $3$. Represent it by main switching values and perform precisely those switches.

It remains to verify that these intervals have no large gaps. Directly, \[ B_{N+1}-B_N=p(D_{N+1})+p(\tau_{N+1})-p(\tau_N) =\lambda N^{2r}+O(N^{2r-1}). \] Thus $B_N\to\infty$, and $\mu>\lambda$ implies that the upper endpoint of $6$ eventually exceeds the lower endpoint of the next interval. Their widths are positive and their lower endpoints increase to infinity. Their union therefore contains every sufficiently large integer. This proves the theorem for degree $r\ge1$.

If $p$ is constant, positivity and the fixed-divisor hypothesis force $p=1$. The polynomial sum is then the number of terms, and the initial Egyptian expansion and operation $1$ give every sufficiently large number of terms. This completes the constant case too.

Verification and outcome

The construction corrects residue classes with finitely many independent switches, then fills actual intervals with the growing family of main switches. Merely proving the switching values have gcd one would not suffice; the finite-window completeness argument and interval overlap close that gap. The old local attempts proved only unboundedness or the constant case; no assertion from them is used without proof.

SOLVED, with the Roth--Szekeres--Graham theorem explicitly external. Taking $\alpha=1$ proves the stated problem; the reconstruction also permits any rational $\alpha>0$ and a prescribed denominator lower bound.

Sources

R. L. Graham, Complete sequences of polynomial values, Duke Math. J. 31 $1964$, 275--285, https://mathweb.ucsd.edu/~ronspubs/64_04_polynomial.pdf. Attributed 2026 switching proof and revised exposition: https://www.overleaf.com/read/gdmnffbshxsq and https://drive.google.com/file/d/1cW2Z7vpTjLQ2Wf6SMb6_nbO9JYlfznnt/view. Current statement and authorship discussion: https://www.erdosproblems.com/forum/discuss/283.

COMPLETION ESTIMATE

COMPLETION: 100%

Round 2 continuation for Erdős Problems #282, #283, #287

Erdős Problem #283

1) ROUND-2 OBJECTIVE

I pursue (A) proof for the constant admissible case $p(n)\equiv 1$. Round 1 produced only a general infinite-family theorem for arbitrary positive-leading-coefficient $p$, but not a cofinite result. The constant case is the cleanest place where the remaining cofinite gap can actually be closed completely by the Round-1 splitting move.

2) Round-1 FOUNDATION USED

I use two Round-1 ingredients.

1. The splitting identity \[ \frac1n=\frac1{n+1}+\frac1{n(n+1)}. \]
2. The fact that if one applies this identity to the largest denominator in a distinct Egyptian fraction expansion, then distinctness is preserved.

3) NEW INSIGHT / TOOL (ROUND-2)

For $p(n)\equiv 1$, the target quantity is simply \[ m=\sum_i p(n_i)=k, \] namely the number of terms. Thus the general polynomial problem collapses to a pure length-realisation problem for Egyptian fraction decompositions of $1$. The Round-1 splitting move increments the number of terms by exactly $1$ while preserving distinctness and the reciprocal sum, so it becomes an exact "length-raising gadget".

4) ATTACK PLAN (ROUND-2)

I prove the exact set of attainable lengths.

1. Show that $1$ term is possible: $\{1\}$.
2. Show that $2$ terms are impossible.
3. Show inductively that every length $k\ge 3$ is possible by repeatedly splitting the current largest denominator.

Since the only admissible constant polynomial is $p\equiv 1$, this completely settles the constant-polynomial case.

5) WORK (ROUND-2)

5.1. The only admissible constant polynomial.

Let $p(n)\equiv c$ be constant. The problem assumes that there is no integer $d\ge 2$ dividing all values $p(n)$. For a constant polynomial this means exactly that $c=1$. Thus the only admissible constant case is \[ p(n)\equiv 1. \]

5.2. Exact classification of attainable lengths.

Let $\mathcal{L}$ be the set of all integers $k\ge 1$ for which there exist distinct positive integers \[ 1\le n_1<\cdots<n_k, \qquad 1=\frac1{n_1}+\cdots+\frac1{n_k}. \] I claim that \[ \mathcal{L}=\{1\}\cup\{3,4,5,\dots\}. \]

First, $1\in\mathcal{L}$ because \[ 1=\frac11. \] Second, $3\in\mathcal{L}$ because \[ 1=\frac12+\frac13+\frac16. \] Now suppose $k\in\mathcal{L}$ with $k\ge 3$. Choose a corresponding decomposition and let $N$ be its largest denominator. Replace the term $1/N$ by \[ \frac1{N+1}+\frac1{N(N+1)}. \] The reciprocal sum is unchanged. Both new denominators are strictly larger than $N$, hence strictly larger than every previously occurring denominator, and they are distinct from each other. So we obtain a distinct Egyptian fraction expansion of $1$ with exactly $k+1$ terms. Therefore $k+1\in\mathcal{L}$.

By induction, every integer $k\ge 3$ lies in $\mathcal{L}$.

It remains to rule out $k=2$. If \[ 1=\frac1a+\frac1b \qquad (1\le a<b), \] then \[ ab=a+b, \] so \[ (a-1)(b-1)=1. \] This has no solution in distinct positive integers. Hence $2\notin\mathcal{L}$.

Thus the classification is proved.

5.3. Consequence for Problem #283 with $p\equiv 1$.

For $p(n)\equiv 1$, one has \[ m=\sum_i p(n_i)=k. \] Hence the attainable $m$ are exactly the attainable lengths. Therefore \[ m=1 \text{ is attainable},\qquad m=2 \text{ is not attainable},\qquad m\ge 3 \text{ are all attainable}. \] In particular the original "for all sufficiently large $m$" statement holds, with exact threshold $M=3$.

6) ADVERSARIAL VERIFICATION

1. Does the induction accidentally reuse denominators? No. The split is applied to the current largest denominator $N$, and both $N+1$ and $N(N+1)$ are $>N$, so they cannot coincide with any previous denominator.
2. Does the split work when $N=1$? I never use it starting from the one-term decomposition $\{1\}$. The induction starts from the three-term decomposition $\{2,3,6\}$.
3. Could there be a hidden two-term solution involving $1$? No. If $a=1$, then $1=1+1/b$ is impossible. The algebraic reduction to $(a-1)(b-1)=1$ also rules this out.
4. Does this solve the full polynomial problem? No. It completely settles only the unique admissible constant case $p\equiv 1$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The general polynomial conjecture remains open, but Round 2 fully closes one genuine subclass that Round 1 did not settle: the admissible constant-polynomial case. For \[ p(n)\equiv 1, \] one has an exact answer: \[ m \text{ is attainable } \Longleftrightarrow m=1 \text{ or } m\ge 3. \] So the constant case is completely solved, with exact threshold $M=3$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 40%

9) REFERENCES

Checked or used in this round:

1. T. F. Bloom, Erdős Problem #283, webpage accessed 2026-03-07.

Erdős Problem #283

1) FORMAL RESTATEMENT

Let $p\in\mathbb{Z}[X]$ be a polynomial with positive leading coefficient, and assume there is no integer $d\ge 2$ such that $d\mid p(n)$ for every $n\ge 1$ (equivalently, $\gcd\{p(1),p(2),\dots\}=1$).

The conjecture asks whether there exists $M$ (depending on $p$) such that for every integer $m\ge M$ one can find distinct integers \[ 1\le n_1<n_2<\cdots<n_k \] with \[ 1=\frac1{n_1}+\cdots+\frac1{n_k} \qquad\text{and}\qquad m=p(n_1)+\cdots+p(n_k). \]

2) QUICK LITERATURE/CONTEXT CHECK

Known special cases and related results recorded in the prompt/context include:

• For $p(x)=x$ (so $m=\sum n_i$), Graham $1963$ proved the conjecture: all sufficiently large $m$ work.
• Cassels $1960$ showed that the stated hypothesis on $p$ implies every sufficiently large integer is a sum of distinct values $p(n_i)$ (without the reciprocal-sum constraint).
• Alekseyev $2019$ proved the conjecture for $p(x)=x^2$ for all $m>8542$.
• Recent work of van Doorn $2025$ investigates quantitative bounds and proves the conjecture for many further linear/quadratic $p$.

The general case for arbitrary admissible $p$ is still listed as open.

3) ATTACK PLAN

1. Closure operations on Egyptian fractions. Use identities like \[\frac1n=\frac1{n+1}+\frac1{n(n+1)}\] (to keep the reciprocal sum equal to $1$) to generate many different denominator sets, while tracking how $\sum p(n_i)$ changes.
2. Additive semigroup approach. Try to show that from one base solution one can generate an additive semigroup of attainable $m$ whose gcd is $1$, hence contains all sufficiently large integers.
3. Use Cassels to hit the $p$-sum, then tune reciprocals. First choose distinct $n_i$ so that $\sum p(n_i)=m$ (possible for large $m$ by Cassels), then adjust the set via splitting/merging operations that preserve the $p$-sum modulo small numbers while forcing the reciprocal sum to become exactly $1$.
4. Search for counterexample polynomials. If false, the obstruction likely comes from subtle congruences tying $p(n)$ to available Egyptian-fraction denominator patterns.

4) WORK

4.1. The divisibility hypothesis is necessary

If there exists $d\ge 2$ dividing $p(n)$ for all $n\ge 1$, then any sum $\sum_i p(n_i)$ is divisible by $d$, so it cannot equal all sufficiently large integers. Thus the "no such $d$" condition is necessary.

4.2. A provable weaker statement: infinitely many $m$ are representable (for any $p$ with positive leading term)

4.3. Why this does not yet solve the conjecture

The above produces an infinite set of attainable $m$ but does not show it is cofinite. To reach "all sufficiently large $m$", one would need a mechanism to adjust $m$ by controlled small increments while keeping $\sum 1/n_i=1$ and denominators distinct.

5) VERIFICATION

• The splitting identity is exact.
• Distinctness under "split the current maximum denominator" is immediate because both new denominators exceed the previous maximum.
• Positivity of $p(n)$ for large $n$ follows from positive leading coefficient.

6) FINAL

UNRESOLVED.

1. Furthest point reached: proved a weaker theorem (infinitely many representable $m$) by a clean closure operation on Egyptian fractions; verified necessity of the "no common divisor" condition.
2. Key gap: no argument was found that the attainable set of $m$ is eventually all integers (cofinite), for a general admissible polynomial $p$.
3. Most promising next step: develop a finite set of "local moves" on Egyptian fraction representations that change $\sum p(n_i)$ by $\pm 1$ (or generate an additive semigroup of increments with gcd $1$), while preserving $\sum 1/n_i=1$.
4. Explicit missing lemma that would close it: existence of a bounded "adjustment gadget"---a finite identity \[\sum_{j=1}^r \frac1{a_j}=\sum_{j=1}^s \frac1{b_j}=\text{(same rational)}\] with all $a_j,b_j$ distinct, such that $\sum p(a_j)-\sum p(b_j)=1$.

7) COMPLETION ESTIMATE

COMPLETION: 25%