Erdős Problem #351

Erdős problem #351

1) FORMAL RESTATEMENT. Let $p\in\mathbb Q[x]$ have positive leading coefficient, including a positive constant polynomial. Show that finite sums of distinct values from $\{p(n)+1/n:n\ge1\}$ contain every sufficiently large integer after any finite deletion.

2) CONTEXT AND THE PRECISE INPUT. The current statement includes the positive-leading-coefficient hypothesis. The negative-polynomial example in the older local file does not answer it. We use the known solution of problem 283, reconstructed with proof in the accompanying 283.tex, in the following strengthened form:

For any integer-valued $q\in\mathbb Q[x]$ on $\mathbb Z$, with positive leading coefficient and $\gcd\{q(n):n\in\mathbb Z\}=1$, any rational $\alpha>0$, and any cutoff $L$, every sufficiently large integer $m$ admits distinct integers $n_i>L$ such that \[ \sum_i q(n_i)=m,\qquad \sum_i\frac1{n_i}=\alpha. \tag{*} \] That writeup proves $(*)$ using the explicitly cited Roth--Szekeres--Graham polynomial completeness theorem; the constant case $q=1$ follows from the Egyptian-fraction length-extension argument there. Here we give the complete reduction, including nonprimitive rational polynomials. This is a known-solution reconstruction, not a new theorem or a claim of a local Lean run.

3) REMOVING FINITELY MANY VALUES. Put $a(x)=p(x)+1/x$. If $p$ is nonconstant, $a'(x)>0$ for all sufficiently large $x$; if $p$ is positive constant, $a'(x)=-x^{-2}<0$. In either case, $a$ is eventually injective. Also, for each fixed value $b$, the equation $p(n)+1/n=b$ becomes the nonzero polynomial equation $n(p(n)-b)+1=0$, so it has only finitely many positive integer solutions. Hence, for any prescribed finite set $B$, there is a cutoff $L$ such that all $a(n)$ with $n>L$ are distinct and avoid $B$.

4) NORMALIZATION AND ALL RESIDUE CLASSES. Choose an integer $D\ge1$ for which $P=Dp\in\mathbb Z[x]$, and let \[ g=\gcd\{|P(n)|:n\in\mathbb Z\}>0,\qquad q=P/g. \] Then $q$ is integer-valued on $\mathbb Z$, has positive leading coefficient, and has no fixed divisor greater than $1$. To see the last assertion, any common divisor of the $q(n)$ would, after multiplication by $g$, contradict the definition of $g$.

For each residue $r\in\{0,\ldots,g-1\}$, fix the positive integer $\alpha_r=r+g$. If an integer $M$ satisfies $M\equiv r\pmod g$, then \[ m=\frac{D(M-\alpha_r)}g \] is an integer tending to infinity with $M$. Apply $(*)$ with $q$, $\alpha_r$ and the above cutoff $L$. Its resulting indices satisfy \[ \sum_i\left(p(n_i)+\frac1{n_i}\right) =\frac gD\sum_iq(n_i)+\alpha_r =\frac gD\frac{D(M-\alpha_r)}g+\alpha_r=M. \] There are only $g$ residue classes, so the maximum of their finitely many thresholds gives one threshold valid for every sufficiently large $M$. The values are distinct and avoid $B$ by the choice of $L$. This proves strong completeness.

5) VERIFICATION AND FINAL. The fixed divisor cannot simply be discarded: the choice of $\alpha_r$ supplies the needed residue corrections. The same argument handles positive constants, and arbitrary finite deletions are of values rather than indices. SOLVED, relative to the explicitly stated and separately reconstructed input $(*)$. No remaining reduction gap is present; the polynomial-completeness theorem used inside the proof of 283 remains an external standard input.

Sources

COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

Literal statement (as written)

Let $p(x)\in\mathbb{Q}[x]$. Define \[ A:={,p(n)+1/n : n\in\mathbb{N},}. \] Call (A) strongly complete if:

For every finite set (B), the set of all finite subset-sums of $A\setminus B$, \[ S(A\setminus B):=\left\{\sum_{t\in X} t \ :\ X\subseteq A\setminus B \text{ finite}\right\}, \] contains all sufficiently large integers, i.e. \[ \forall, B\text{ finite}\ \exists N_B\in\mathbb{N}\ \forall m\in\mathbb{Z}\ (m\ge N_B \implies m\in S(A\setminus B)). \]

Ambiguity/misstatement 1 (dummy variable): The problem text writes $\sum_{n\in X} n$ with $X\subseteq A\setminus B$. Since (X) consists of elements of (A) (rationals), the summand must be an element of (X), not an index (n). The minimal correction is to write $\sum_{t\in X} t$.

Ambiguity/misstatement 2 ($\mathbb{N}$ and $1/n$): Since $1/n$ appears, we must take $\mathbb{N}={1,2,3,\dots}$ (otherwise $n=0$ is invalid).

Ambiguity/misstatement 3 (missing growth/positivity hypothesis on (p)): As written, (p) is arbitrary in $\mathbb{Q}[x]$, including polynomials with negative leading coefficient. Then $p(n)+1/n$ can be eventually negative and the claim becomes trivially false (see below).

Minimal corrected statement consistent with standard conventions

A minimal fix consistent with “complete sequences” conventions is to assume $p(n)+1/n>0$ for all sufficiently large (n), e.g. that (p) has positive leading coefficient (so $p(n)\to+\infty$):

If $p\in\mathbb{Q}[x]$ has positive leading coefficient, is $A={p(n)+1/n:n\ge1}$ strongly complete?

I will disprove the literal statement (which quantifies over all $p\in\mathbb{Q}[x]$ with no sign restriction).

---

2) QUICK LITERATURE/CONTEXT CHECK (browsing used)

The Erdős Problems site lists this as open in general, and notes Graham’s result for $p(n)=n$. ([erdosproblems.com][1]) However, the forum discussion explicitly records that the literal formulation is false: it says the problem was “disproved … with the polynomial $p(x):=-x$” and that one should assume the leading coefficient is nonnegative. ([erdosproblems.com][2])

(So a counterexample is already known/standard; I’ll give a fully rigorous disproof below.)

---

3) ATTACK PLAN

Disproof / counterexample strategies

1. Make (A) bounded above (e.g. all elements $\le 0$). Then every finite subset-sum is $\le 0$, so no large positive integers are representable. 2. Even weaker: ensure (A) has only finitely many positive elements, so subset-sums have a finite maximum.

Proof strategies (not pursued, since disproof will succeed)

* Try to reduce to known partition/complete-sequence results (Graham-type constructions) and build Egyptian-fraction-type cancellations of $\sum 1/n$ to hit integers.

Chosen path: Strategy $1$ with $p(x)=-x$.

---

4) WORK (explicit counterexample + verification)

Counterexample

Take \[ p(x):=-x\ \in\mathbb{Q}[x]. \] Then for each integer $n\ge 1$, \[ p(n)+\frac1n=-n+\frac1n=\frac{1-n^2}{n}=-\frac{n^2-1}{n}. \]

Lemma 1: Every element of (A) is $\le 0$, and in fact (A$\subseteq$$-\infty,0]$.

Proof.

* For $n=1$: $-1+1=0$. * For $n\ge 2$: $n^2-1>0$, so $-\frac{n^2-1}{n}<0$.

Thus $p(n)+1/n\le 0$ for all $n\ge 1$, hence (A$\subseteq$$-\infty,0]$. ∎

Lemma 2: For any finite set (B), every finite subset-sum of $A\setminus B$ is $\le 0$.

Proof. Fix any finite set (B) (no assumption needed that $B\subseteq A$). Then (A$\setminus$ B$\subseteq$ A$\subseteq$$-\infty,0]$ by Lemma 1.

Let $X\subseteq A\setminus B$ be finite. Every term $t\in X$ satisfies $t\le 0$. Therefore \[ \sum_{t\in X} t \le 0, \] since a finite sum of nonpositive real numbers is nonpositive. Hence \[ S(A\setminus B)=\left\{\sum_{t\in X} t : X\subseteq A\setminus B\text{ finite}\right\}\subseteq (-\infty,0]. \] ∎

Proposition: (A) is not strongly complete.

Proof. Strong completeness would require (in particular, taking $B=\varnothing$) that there exists (N) such that every integer $m\ge N$ lies in (S(A)).

But by Lemma 2 with $B=\varnothing$, we have (S(A)$\subseteq$$-\infty,0]$. Hence no positive integer $m\ge 1$ is in (S(A)). In particular, it is impossible that all integers $m\ge N$ (which include positive integers) belong to (S(A)).

Therefore (A) is not strongly complete. ∎

This contradicts the literal statement “for every $p\in\mathbb{Q}[x]$, (A) is strongly complete.”

---

5) VERIFICATION (adversarial checks)

* Quantifiers: The claim (literal) is $\forall p\in\mathbb{Q}[x]$ [strong completeness]. I exhibited a single $p(x)=-x$ and proved $\neg$[strong completeness], so the universal statement is falsified. * Definition of “sufficiently large integers”: Standard meaning is: $\exists N$ such that $\forall m\in\mathbb{Z}$ with $m\ge N$. My argument shows no positive integer is representable, so certainly not all integers $\ge N$ for any (N). * Edge case (B): Strong completeness requires the property for every finite (B). My argument is stronger: it fails already for $B=\varnothing$, and in fact Lemma 2 shows it fails for every finite (B). * Notation issue ($\sum_{n\in X}$n): If one mistakenly read (n) as an “index”, the expression is ill-typed since $X\subseteq A\setminus B$ consists of rationals, not indices. The only coherent reading is “sum the elements of (X)”, which is what I used.

No hidden assumptions remain.

---

6) FINAL

COUNTEREXAMPLE/DISPROOF

Take $p(x)=-x$. Then (A={-n+1/n:n$\ge$1}$\subseteq$$-\infty,0]$, so every finite subset-sum of $A\setminus B$ is $\le 0$ for any finite (B). Hence $S(A\setminus B)$ contains no positive integers and therefore cannot contain “all sufficiently large integers.” Thus the statement as written is false.

[1]: https://www.erdosproblems.com/351 " Erdős Problem #351 " [2]: https://www.erdosproblems.com/forum/thread/351 "

Erdős Problem #351 - Discussion thread

"

Yes — for the statement as written (quantifying over all $p\in\mathbb{Q}[x]$ with no positivity/growth condition), the counterexample $p(x)=-x$ really does kill it, and the calculations are straightforward. I’ll re-check them line by line.

Step 0: Fix the only coherent interpretation of the subset-sum

Since $A\subset\mathbb{Q}$, a “finite $X\subseteq A\setminus B$” is a finite set of rationals, so the subset-sums are \[ S(A\setminus B)=\left\{\sum_{t\in X} t:\ X\subseteq A\setminus B \text{ finite}\right\}. \] (Your pasted statement has $\sum_{n\in X} n$, but that’s just a dummy-variable typo; it must mean summing the elements of (X).)

Step 1: Compute (A) for $p(x)=-x$

Let $p(x)=-x$. Then for each $n\ge 1$, \[ a_n:=p(n)+\frac1n=-n+\frac1n. \] Rewrite it as a single fraction: \[ -n+\frac1n=\frac{-n^2+1}{n}=-\frac{n^2-1}{n}. \]

Step 2: Check the sign of every term

* For $n=1$: \[ a_1=-1+1=0. \] * For $n\ge 2$: we have $n^2-1>0$ and $n>0$, hence $\frac{n^2-1}{n}>0$, so \[ a_n=-\frac{n^2-1}{n}<0. \]

Therefore, \[ A={a_n:n\ge 1}\subseteq (-\infty,0]. \]

(Concrete check: $a_2=-2+\tfrac12=-\tfrac32$, $a_3=-3+\tfrac13=-\tfrac83$, etc.)

Step 3: Subset-sums of nonpositive numbers are nonpositive

Take any finite set (B) (whether or not it’s a subset of (A); set difference still makes sense). Then \[ A\setminus B\subseteq A\subseteq (-\infty,0]. \] Now take any finite subset $X\subseteq A\setminus B$. Every element $t\in X$ satisfies $t\le 0$, so the finite sum satisfies \[ \sum_{t\in X} t\le 0. \] Hence \[ S(A\setminus B)\subseteq (-\infty,0]. \]

Step 4: Conclude “not strongly complete”

“Strongly complete” requires: for every finite (B), the set $S(A\setminus B)$ contains all sufficiently large integers — in particular, it would have to contain all sufficiently large positive integers.

But we just proved (S$A\setminus B$$\subseteq$$-\infty,0]$, so it contains no positive integer at all (not even $1$). Therefore it cannot contain all integers $\ge N$ for any (N). So (A) is not strongly complete.

That is a valid disproof of the literal universal statement “for every $p\in\mathbb{Q}[x]$, (A) is strongly complete.”

Cross-check against the problem’s discussion

The Erdős Problems forum thread for #351 explicitly notes that the wording as stated was “disproved … with the polynomial $p(x):=-x$” and that one should assume the leading coefficient is nonnegative to avoid this trivial obstruction. ([Erdős Problems][1])

---

Important nuance

If by “the conjecture” you mean the intended corrected version with an added hypothesis like “(p) has nonnegative/positive leading coefficient” (so $p(n)+1/n$ is eventually positive), then my $p(x)=-x$ example does not apply to that corrected conjecture. It only disproves the literal statement you pasted.

[1]: https://www.erdosproblems.com/forum/thread/351 "

Erdős Problem #351 - Discussion thread

"

1) FORMAL RESTATEMENT

1.1 Literal statement on the page (with notation fixed)

Let $p(x)\in \mathbb Q[x]$. Define \[ A ;:=; {, p(n)+1/n ;:; n\in\mathbb N ,}, \] where $\mathbb N={1,2,3,\dots}$.

For a set $S\subset\mathbb R$, write \[ \operatorname{FS}(S);:=;\left\{\sum_{x\in X} x ;:; X\subseteq S\ \text{finite}\right\} \] (the set of finite subset sums of (S)). (The website text uses ($\sum_{n\in X}$n) even though $X\subseteq A$ consists of rationals; the minimal correction is ($\sum_{x\in X}$x).)

Strong completeness of (A) means: \[ \forall\ \text{finite }B\subseteq A\ \ \exists N_B\in\mathbb N\ \ \forall M\in\mathbb Z,\ M\ge N_B:\ M\in \operatorname{FS}(A\setminus B). \] (If (B) is allowed to be any finite set of reals, it is equivalent, since removing points not in (A) changes nothing.)

1.2 “Corrected/intent” version you asked me to prove

A minimal formalization of the intended correction is:

Corrected conjecture (intent). If $p\in\mathbb Q[x]$ has positive leading coefficient (equivalently $p(n)+1/n>0$ for all sufficiently large (n)), then $A={p(n)+1/n:n\in\mathbb N}$ is strongly complete.

This excludes the trivial obstruction $p(x)=-x$ noted in the forum thread. ([Erdős Problems][1])

1.3 Stress points / edge cases

* If (p) has negative leading coefficient, then $p(n)+1/n\to -\infty$, so no large positive integer can be a subset sum. This kills the literal version. * Strong completeness is equivalent to: for every $m\in\mathbb N$, the tail \[ A_{\ge m}:={p(n)+1/n:n\ge m} \] is (ordinary) complete (contains all sufficiently large integers in its finite subset sums). This reduction is standard and I prove it below.

---

2) QUICK LITERATURE/CONTEXT CHECK (web available)

* The Erdős Problems forum thread explicitly says: “This problem was disproved … with $p(x)=-x$” and that one should assume nonnegative leading coefficient; i.e., the literal formulation is false but the “corrected” one is the intended open direction. ([Erdős Problems][1]) * Graham’s 1963 paper proves the key partition theorem (and stronger “tail” versions): every sufficiently large integer can be written as a sum of distinct integers whose reciprocals sum to a prescribed rational $\alpha$, with all parts $\ge \beta$. This is Theorem 3 of Graham $1963$. * In the Remarks of Graham $1963$, he explicitly notes a conjectural strengthening where the sum of denominators is replaced by sum of values of a polynomial (f) with positive leading coefficient; he says “very little is known” about that. This remark is directly aligned with the corrected conjecture you’re asking for.

Given these sources, the broad corrected conjecture is consistent with the literature as being nontrivial and (apparently) open in general; special cases are known (e.g. $p(n)=n$ from Graham).

---

3) ATTACK PLAN

Proof-track strategies

1. Linear case reduction to Graham’s Theorem 3. If $p(n)=c n$, then any Graham partition of an integer (S) with reciprocal sum $\alpha$ immediately yields a subset sum equal to (cS+$\alpha$). By choosing $(S,\alpha)$ appropriately one can force (cS+$\alpha$) to be any large integer. This should give a complete, rigorous proof at least for homogeneous linear (p).

2. General polynomial via “block” integers. Try to construct infinitely many disjoint “blocks” $X_i\subseteq A_{\ge m}$ whose sums are integers $b_i$, and then make $(b_i)$ a complete integer sequence (e.g. via a Brown-type criterion). The hard step is forcing $\sum_{n\in I} p(n)$ to hit prescribed values under reciprocal constraints—this resembles Graham’s own “2′ ” conjectural remark.

Disproof-track strategies

1. Congruence/denominator obstructions. Try to show that for some positive-leading (p), every subset sum has a nonzero fractional part (mod 1), or misses a residue class of integers. 2. Finite-removal sabotage. Try to find a finite $B\subseteq A$ such that the tail cannot represent integers (e.g. by forcing reciprocal sums to be too small, etc.). 3. Computation-guided search. Test small (p) and small truncations to look for structural impossibilities (not a proof, but may inspire a construction).

Choice: I can fully execute strategy $1$ for the homogeneous linear case (p(x)=cx). For general (p), the natural next lemma is essentially Graham’s conjectural polynomial-strengthening, and I cannot currently close that gap.

---

4) WORK

4.1 Tail-completeness implies strong completeness

Lemma 4.1 (Tail criterion). Let $A={a_n:n\in\mathbb N}$ be a set indexed by $\mathbb N$. Suppose that for every $m\in\mathbb N$ there exists (N(m)) such that every integer $M\ge N(m)$ lies in $\operatorname{FS}({a_n:n\ge m})$. Then (A) is strongly complete: for every finite $B\subseteq A$, $\operatorname{FS}(A\setminus B)$ contains all sufficiently large integers.

Proof. Let $B\subseteq A$ be finite. Let \[ I_B:={n\in\mathbb N: a_n\in B}. \] This is a finite subset of $\mathbb N$. Let $m:=1+\max I_B$ (if $B=\emptyset$, take $m=1$). Then ${a_n:n\ge m}\subseteq A\setminus B$. Hence \[ \operatorname{FS}({a_n:n\ge m})\subseteq \operatorname{FS}(A\setminus B). \] By hypothesis, every integer $M\ge N(m)$ lies in the left-hand side, hence also in $\operatorname{FS}(A\setminus B)$. ∎

So to prove strong completeness of $A={p(n)+1/n}$, it suffices to prove: for each (m), the tail ${p(n)+1/n:n\ge m}$ is complete.

---

4.2 Literal statement is false (for context)

This is not the “corrected” version, but it’s worth recording cleanly.

Proposition 4.2. With no sign restriction on (p), the statement “$A={p(n)+1/n}$ is strongly complete” is false.

Proof (explicit counterexample). Take $p(x)=-x$. Then for $n\ge 2$, \[ p(n)+1/n=-n+1/n<0, \] and for $n=1$, $p(1)+1=0$. Hence every finite subset sum of (A) is $\le 0$. Therefore ($\operatorname{FS}$$A\setminus B$$\subseteq$ $-\infty,0]$ for any (B), so it cannot contain all sufficiently large positive integers. ∎

This matches the forum remark about AlphaProof’s counterexample $p(x)=-x$. ([Erdős Problems][1])

---

4.3 A rigorous proof for a nontrivial class: $p(x)=c x$ (homogeneous linear)

This does not prove the full corrected conjecture for all polynomials, but it is a complete proof for an infinite family of positive-leading (p), using Graham’s Theorem 3.

Input theorem (Graham 1963, Theorem 3)

From Graham’s paper:

For any positive rationals $\alpha$ and $\beta$ there exists an $r=r(\alpha,\beta)$ such that if $n>r$ then there exist distinct integers $a_1<\cdots<a_k$ with $a_1\ge \beta$, \[ n=a_1+\cdots+a_k,\qquad \alpha=\frac1{a_1}+\cdots+\frac1{a_k}. \] This is exactly Theorem 3 in the PDF.

I will use this theorem as a black box.

Theorem 4.3 (Strong completeness for (p(x)=$\frac{u}{v}$x))

Let $u,v\in\mathbb N$ with $\gcd(u,v)=1$. Define \[ p(x)=\frac{u}{v}x,\qquad A:=\left\{\frac{u}{v}n+\frac1n: n\in\mathbb N\right\}. \] Then (A) is strongly complete.

Proof. By Lemma 4.1 it suffices to prove: for every $m\in\mathbb N$, the tail \[ A_{\ge m}:=\left\{\frac{u}{v}n+\frac1n: n\ge m\right\} \] is complete.

Fix $m\in\mathbb N$. For each integer (t) with $1\le t\le u$, define the positive rational \[ \alpha_t:=\frac{t}{v}. \] Let $r_t:=r(\alpha_t,m)$ be the threshold given by Graham’s Theorem 3 for the pair $(\alpha_t,\beta=m)$. Define \[ R:=\max_{1\le t\le u} r_t. \] (This is finite because there are only finitely many (t).)

Now let $M\in\mathbb N$ be an integer so large that \[ S:=\frac{vM-u}{u} ;>; R. \] (For instance, it suffices that $M> \frac{u(R+1)}{v}+1$.)

Next choose $t\in{1,2,\dots,u}$ so that \[ t \equiv vM \pmod{u}. \] Such a (t) exists because residues modulo (u) form a complete system and we can choose the unique representative in ${1,\dots,u}$ (take $t=u$ if (vM$\equiv$ 0$\pmod u$)).

Define \[ S:=\frac{vM-t}{u}. \] Then $S\in\mathbb Z$ because (u$\mid$ (vM-t)). Also, since $1\le t\le u$, we have \[ S=\frac{vM-t}{u}\ \ge\ \frac{vM-u}{u}\ >\ R\ \ge\ r_t. \] Therefore Graham’s Theorem 3 (applied with $\alpha=\alpha_t=t/v$, $\beta=m$, and $n=S$) yields distinct integers \[ m\le n_1<\cdots<n_k \] such that \[ S=n_1+\cdots+n_k,\qquad \frac{t}{v}=\frac1{n_1}+\cdots+\frac1{n_k}. \]

Now consider the subset (X={$\frac{u}{v}$n_i+$\frac1{n_i}$:1$\le$ i$\le$ k}$\subseteq$ $A_{\ge m}$). Its sum is \[ \sum_{i=1}^k\left(\frac{u}{v}n_i+\frac1{n_i}\right) =\frac{u}{v}\sum_{i=1}^k n_i + \sum_{i=1}^k \frac1{n_i} =\frac{u}{v}S + \frac{t}{v} =\frac{uS+t}{v} =\frac{vM}{v} =M. \] Thus $M\in \operatorname{FS}(A_{\ge m})$.

We have shown: for all sufficiently large integers (M), $M\in \operatorname{FS}(A_{\ge m})$. Hence $A_{\ge m}$ is complete. Since (m) was arbitrary, Lemma 4.1 implies (A) is strongly complete. ∎

What this proves toward the corrected conjecture: the corrected conjecture holds for the infinite family of positive-leading polynomials $p(x)=c x$ with $c\in\mathbb Q_{>0}$.

---

4.4 Where the general corrected conjecture gets stuck

To prove the corrected conjecture for a general polynomial (p) of degree $\ge 2$, the linear trick above fails because $\sum p(n_i)$ is no longer determined by $\sum n_i$.

A natural sufficient statement would be:

For each fixed (m) and each large integer (N), one can find distinct integers $n_i\ge m$ with \[ N-1=\sum_i p(n_i),\qquad 1=\sum_i \frac1{n_i}. \] Then $N=\sum_i\left(p(n_i)+\frac1{n_i}\right)$.

But Graham’s own Remarks in the 1963 paper explicitly point to this kind of strengthening as conjectural: he suggests replacing “$n=a_1+\cdots+a_k$” by “$n=f(a_1)+\cdots+f(a_k)$” for integer-valued polynomials (f) with positive leading coefficient, and says “very little is known”. This is essentially the first genuine obstruction to turning the linear proof into a general polynomial proof.

---

4.5 Phase 1 “fast reality check” computations (not a proof)

I did quick brute-force subset-sum searches on the truncated sets \[ A_N:={p(n)+1/n:1\le n\le N} \] for a few small polynomials $e.g. (p(n)=n,n^2,n^3, n/2,\dots)$ with $N=14$, checking which integers appear as subset sums. For these tiny truncations, only a few integers appear (e.g. for $p(n)=n$, the integers ${0,2,12,14,25,27,\dots}$ occur), which is not surprising: the known theorems are asymptotic and typically use very large denominators.

This does not suggest a counterexample to the corrected conjecture; it just confirms the problem is not “trivially true” at small scales.

---

5) VERIFICATION (adversarial check)

5.1 Quantifier and set-difference checks in Theorem 4.3

* Tail condition: For each fixed (m), I produced a threshold $M_0(m)$ such that all integers $M\ge M_0(m)$ lie in $\operatorname{FS}(A_{\ge m})$. This is exactly “completeness of the tail”. * Use of Graham’s theorem: Graham’s Theorem 3 provides the existence of distinct $n_i\ge m$ with prescribed sum (S) and prescribed reciprocal sum $\alpha_t$, once $S>r(\alpha_t,m)$. I ensured $S>R\ge r_t$. * Arithmetic integrity: The key step is choosing $t\in{1,\dots,u}$ with (t$\equiv$ vM$\pmod u$), ensuring (S=(vM-t)/u$\in\mathbb Z$), and then \[ \frac{u}{v}S+\frac{t}{v}=M. \] This is exact, not asymptotic.

5.2 Strong completeness from tail completeness

* Lemma 4.1 is correct: if $B\subseteq A$ is finite, then after removing (B) you still retain a full tail $A_{\ge m}$ for (m) bigger than all removed indices. Subset sums of a subset are included in subset sums of the whole set.

5.3 Boundary cases

* If $u=1$, the argument still works; (t) is forced to be $1$. * If $v=1$, then $p(n)=u n$ and $\alpha_t=t$ is an integer; Graham’s theorem applies to any positive rational, including integers, so still fine.

No hidden assumptions about monotonicity, distinctness of values, etc., were used: we sum over distinct indices, hence distinct elements in the set definition.

---

FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here: The corrected conjecture is true for the infinite family $p(x)=c x$ with $c\in\mathbb Q_{>0}$ (Theorem 4.3), using Graham’s Theorem 3.

(ii) Exact first gap blocking a proof of the full corrected conjecture: For $\deg p\ge 2$, one needs a method to force simultaneously (or in a controlled coupled way) the conditions on $\sum p(n_i)$ and $\sum 1/n_i$ so that $\sum(p(n_i)+1/n_i)$ hits every large integer. This is essentially the kind of strengthening Graham himself flags as conjectural (“replace $n=a_1+\cdots+a_k$ by $n=f(a_1)+\cdots+f(a_k)$ for polynomials (f)”), and he states that very little is known.

(iii) Top 3 next moves (concrete lemmas to target):

1. Prove a “polynomial Graham partition” statement: for fixed (m) and $\alpha\in\mathbb Q_{>0}$, show all sufficiently large integers (N) admit distinct $n_i\ge m$ with $\sum 1/n_i=\alpha$ and $\sum p(n_i)=N$. (This would essentially settle the conjecture.) 2. Develop a “block” construction: build infinitely many disjoint sets $S_j$ with $\sum_{n\in S_j} (p(n)+1/n)\in\mathbb Z$ and with these block-sums forming a complete integer sequence. 3. Try degree-by-degree: adapt the known $p(n)=n^2$ solution pattern (forum mentions it follows from Graham + Alekseyev) to $p(n)=n^3$ or to broader classes, looking for the exact structural ingredient that enables the $n^2$ case. ([Erdős Problems][1])

(iv) What a minimal counterexample to the corrected conjecture would likely look like (if it exists): It would need a positive-leading polynomial (p) for which, after removing finitely many initial terms, the coupled constraint \[ \sum_{n\in I}\left(p(n)+\frac1n\right)\in\mathbb Z \] becomes so rigid that the integer subset sums miss infinitely many large integers—most plausibly via a structural obstruction modulo 1 linking $\sum p(n)$ and $\sum 1/n$ for all admissible finite (I). I did not find such an obstruction.

[1]: https://www.erdosproblems.com/forum/thread/351 "

Erdős Problem #351 - Discussion thread

"