Erdős problem 244 — live-page audit, explicit algebraic bases, and verification
Access/research date: 2026-07-26 (UTC).
Claim labels used below:
- (a) elementary-rigorous: proved in this report from elementary facts.
- (b) rigorous-modulo-named-theorem: the deduction is rigorous, conditional only on the accurately cited theorem.
- (c) plausible/structural-unverified: a heuristic or a literature-search qualification, not a theorem.
- (d) computational-only: an exact finite computation, with no asymptotic implication.
0. Mandatory live-page gate
I fetched the rendered live page through the Bright Data browser path, not through direct
datacenter curl. I separately fetched the discussion thread and the page's dynamically
loaded bibliography entries.
Verbatim current statement
The following is copied verbatim from the live page's “View the LaTeX source” rendering:
> Let $C>1$. Does the set of integers of the form $p+\lfloor C^k\rfloor$, for some prime $p$ and $k\geq 0$, have density $>0$?
Current status and participation metadata
The live record at erdosproblems.com/244, accessed
2026-07-26, showed:
- status: OPEN;
- claimed proofs: 0;
- interested in collaborating: None;
- currently working on this problem: None;
- likes: Dogmachine;
- “looks difficult”: Dogmachine;
- “looks tractable”: None;
- “results could be formalisable”: None;
- “working on formalising”: None;
- formalised statement: Yes;
- last page edit: 28 October 2025.
Therefore the mandatory stop condition did not trigger.
Results and sources listed on the live page
The page says that Kalmár asked Erdős the question, Erdős expected an affirmative answer,
Romanoff proved the integer-\(C\) case, and Ding proved the assertion for almost every
\(C>1\).
The bibliography widgets gave:
[Er61]P. Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató
Int. Közl. 6 (1961), 221–254; the problem is item (14) on p. 230.
[Ro34]N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie,
Math. Ann. 109 (1934), 668–678.
[Di25]Y. Ding, On a Romanoff type problem of Erdős and Kalmár,
arXiv:2503.22700 (2025). The arXiv record has since changed title and reached v3;
see the literature audit below.
The two comments
The separate discussion thread contained
two comments and no proof claim.
- (c) Dogmachine (15 Oct 2025) observed that, unlike a problem with only countably
many candidate exceptions, this problem has uncountably many possible exceptional
bases, making a pointwise elimination ambitious.
- (c) Terence Tao (11 Aug 2025) identified a possible obstruction: the values
\(\lfloor C^k\rfloor\) might be highly concentrated in one residue class modulo \(W\).
He suggested that concentration for many \(W\) could force density bounds involving
\(\varphi(W)/W\), and that ruling this out may be related to Mahler's \(3/2\) problem.
The site explicitly labels comments as unverified; I use this only as structural
motivation.
1. What “density” means here
Write
\[ \underline d(A)=\liminf_{x\to\infty}\frac{|A\cap[1,x]|}{x}. \]The site's definitions distinguish natural density from lower density. Nevertheless,
the live remarks call Romanoff's and Ding's results affirmative answers, while those
sources explicitly prove positive lower asymptotic density. Thus the intended
Erdős–Kalmár formulation in the cited literature is
\[ \underline d\!\left(\{p+\lfloor C^k\rfloor:p\in\mathbb P,\ k\geq0\}\right)>0. \]All positive-density conclusions in this report are in that precise sense. If one insists
on the strictly literal stronger demand that a natural-density limit must exist, neither
the page's cited results nor the result below establishes that extra existence assertion.
2. Primary-source literature audit
Erdős and Romanoff
I downloaded Erdős's original 34-page paper from the
Page 230, item (14), records Romanoff's integer-base theorem and Kalmár's real-base
question, followed by Erdős's statement that the answer was “no doubt” affirmative but
that he could not prove it.
Romanoff's original article exists with DOI
10.1007/BF01449161; its bibliographic data and
full-text record are also at EuDML. (b) Its theorem,
as quoted independently by Erdős, Ballot–Luca, and Ding, gives positive lower density
for \(p+a^k\) for every integer \(a>1\).
Ding's current preprint
The authoritative arXiv API and downloaded PDF show that arXiv:2503.22700 is now
version 3, dated 19 July 2026, under the title
Integer parts of real powers in two Erdős problems of Romanoff type.
- (b) Ding's Theorem 1.1 proves for almost every \(y>1\) the quantitative bound
\[ \underline d(S_y)\geq \frac{1}{\log y+C_{\rm sv}\zeta(2)/\zeta(4)}, \]
where \(C_{\rm sv}\) is the paper's Selberg-sieve constant.
- (b) Ding's Theorem 1.2 proves that for
\(\phi=(1+\sqrt5)/2\), the complement of \(S_\phi\) also has positive lower
density, with the displayed lower bound
\(x/7845692610-O(\log x)\) for its counting function.
The second fact is compatible with the positive-density result for \(S_\phi\) below:
both the representable and non-representable sets can have positive lower density.
The linear-recurrence theorem used here
I downloaded the complete primary-source paper:
Christian Ballot and Florian Luca,
On the sumset of the primes and a linear recurrence,
Acta Arith. 161 (2013), 33–46,
Its Theorem 1 states: (b) if \((u_n)\) is a nondegenerate integral linear recurrence
whose minimal characteristic polynomial is monic over \(\mathbb Z\) with distinct roots
(and whose sole root has modulus at least \(2\) in degree one), then
\[ \mathbb P+\{u_n:n\geq0\} \]has positive lower asymptotic density.
A newer independent cross-check is Rui-Jing Wang,
On integers of the form \(p+L_{k_1^{r_1}}+\cdots+L_{k_t^{r_t}}\),
Period. Math. Hungar. (published 14 May 2026),
DOI 10.1007/s10998-026-00718-9. (b) Its publisher abstract explicitly gives positive
lower density for prime-plus-Lucas sums, and in the one-Lucas case gives a positive
proportion of unique representations.
Search miss / novelty qualification
I searched exact-title and topic combinations involving “Erdős–Kalmár,” “Pisot,”
“Salem,” “Romanoff,” “floor powers,” and “sum of a prime,” and inspected Ding's current
reference list. (c) I did not find a source explicitly stating the Pisot/Salem
corollary proved below. This is not evidence that it has never been observed, so I make
no novelty claim. It is a direct but apparently useful consequence of Ballot–Luca.
Downloaded-source hashes used in the audit:
bc308afb011a6404ae610ed681866e5f56d2fd5dd450bd9d92731d1128c79222 Ding arXiv v3 PDF
8032a5553e0e810686f9b6c89e04e11e905367e8162511ecb3737b1f329bfb7f Ballot–Luca PDF
6f6dac75cb03edcaf1d7e13509ea9001937248cea1fd5e932b386a6a0a7a1007 Erdős 1961 PDF
3. Main partial result
Theorem
**(b) Let \(C>1\) be a real algebraic integer. Suppose every conjugate of \(C\), other
than \(C\) itself, has modulus at most \(1\). Then**
\[ \underline d\{p+\lfloor C^k\rfloor:p\in\mathbb P,\ k\geq0\}>0. \]Consequently Erdős problem 244 has an affirmative answer for every Pisot number and
every Salem number (and, already by Romanoff, every integer \(C>1\)).
The proof has one elementary transfer lemma and one application of Ballot–Luca.
Lemma: finite-valued perturbations preserve Romanoff positivity
(a) Let \(u_n,a_n\) be integer sequences and suppose that, after deletion of finitely
many indices,
\[ a_n-u_n\in F \]for a fixed finite set \(F\subset\mathbb Z\). If
\(\mathbb P+\{u_n\}\) has positive lower density, then
\(\mathbb P+\{a_n\}\) has positive lower density. More precisely, if the former lower
density is \(\delta\), the latter is at least \(\delta/|F|\).
Proof. Delete a finite prefix on which the terms are not positive. This does not change
the conclusion: a finite union of fixed translates of the primes has density zero.
For each \(c\in F\), let
\[ I_c=\{n:a_n-u_n=c\},\qquad A_c=\mathbb P+\{u_n:n\in I_c\}. \]Then
\[ \mathbb P+\{u_n\}=\bigcup_{c\in F}A_c,\qquad \mathbb P+\{a_n\}\supseteq\bigcup_{c\in F}(A_c+c). \]A fixed translation changes a counting function on \([1,x]\) by \(O_c(1)\). Therefore
\[ \begin{aligned} |(\mathbb P+\{a_n\})\cap[1,x]| &\geq \max_{c\in F}|(A_c+c)\cap[1,x]|\\ &\geq \frac1{|F|}\sum_{c\in F}|A_c\cap[1,x]|-O_F(1)\\ &\geq \frac1{|F|} |(\mathbb P+\{u_n\})\cap[1,x]|-O_F(1). \end{aligned} \]Taking a liminf proves the lemma. \(\square\)
Trace construction
Let the conjugates of \(C\) be
\[ \alpha_1=C,\alpha_2,\ldots,\alpha_d. \]Define \(i\sim j\) when \(\alpha_i/\alpha_j\) is a root of unity. Choose \(m\geq1\)
divisible by the orders of all such root-of-unity quotients, and put
\[ u_n=\operatorname{Tr}_{\mathbb Q(C)/\mathbb Q}(C^{mn}) =\sum_{i=1}^d\alpha_i^{mn}. \]The following structural facts are elementary.
1. (a) Every \(u_n\) is an integer: it is both a rational number (a field trace)
and an algebraic integer.
2. (a) After equal values \(\alpha_i^m\) are merged, write the distinct values as
\(\beta_1,\ldots,\beta_r\), with multiplicities \(e_1,\ldots,e_r\). Then
\[ u_n=\sum_{j=1}^r e_j\beta_j^n. \]
No quotient \(\beta_i/\beta_j\), \(i\ne j\), is a root of unity. Otherwise
\((\alpha_i/\alpha_j)^m\) would be a root of unity and the original roots would
have belonged to the same class.
3. (a) The polynomial
\[ Q(X)=\prod_{j=1}^r(X-\beta_j) \]
lies in \(\mathbb Z[X]\). The set of distinct \(\beta_j\)'s is Galois-stable, so
the coefficients are rational; they are also algebraic integers.
Since all \(e_j\ne0\), \(Q\) is the minimal characteristic polynomial of
\((u_n)\). Its roots are distinct and the recurrence is nondegenerate.
4. (a) If \(r=1\), then \(d=1\). Indeed, a conjugate in the same root-of-unity
class as \(C\) has modulus \(C>1\), contradicting the assumed modulus bound unless
there is no other conjugate. Thus the degree-one root is \(C^m\geq2\).
All hypotheses of Ballot–Luca Theorem 1 now hold. Hence
\[ \delta_u:=\underline d\bigl(\mathbb P+\{u_n:n\geq0\}\bigr)>0. \tag{3.1} \]This is the single named-theorem dependency in the new result.
The floor sequence is a finite-valued perturbation
Put
\[ R_n=\sum_{i=2}^d\alpha_i^{mn}. \]It is real because \(R_n=u_n-C^{mn}\), and the conjugate bound gives
\[ |R_n|\leq d-1. \]Since \(u_n=C^{mn}+R_n\) is an integer,
\[ \lfloor C^{mn}\rfloor =u_n+\lfloor-R_n\rfloor. \tag{3.2} \]Thus
\[ \lfloor C^{mn}\rfloor-u_n\in \{-d+1,-d+2,\ldots,d-1\}, \]a set of at most \(2d-1\) integers. Applying the elementary transfer lemma to (3.1)
and (3.2) gives
\[ \underline d\bigl(\mathbb P+\{\lfloor C^{mn}\rfloor:n\geq0\}\bigr) \geq \frac{\delta_u}{2d-1}>0. \]This sumset is contained in the sumset from problem 244, because \(mn\) is an allowed
exponent. The theorem follows.
For a Pisot number, \(|\alpha_i|<1\) for \(i\geq2\), so \(R_n\to0\).
(a) After finitely many indices the correction in (3.2) belongs to
\(\{-1,0\}\), improving the transfer loss to a factor of at most \(2\).
4. Concrete explicit bases
Golden ratio
Let \(L_0=2,L_1=1,L_{k+2}=L_{k+1}+L_k\) and
\(\psi=(1-\sqrt5)/2=-\phi^{-1}\). Binet's identity is
\[ L_k=\phi^k+\psi^k. \]Because \(0<|\psi|^k<1\) for \(k\geq1\), with sign determined by the parity of \(k\),
\[ \boxed{\lfloor\phi^k\rfloor= \begin{cases} L_k,&k\text{ odd},\\ L_k-1,&k\text{ even}, \end{cases}} \tag{4.1} \]also valid at \(k=0\).
Let
\[ A=\mathbb P+\{L_k:k\text{ odd}\},\qquad B=\mathbb P+\{L_k:k\text{ even}\}. \]Then (a)
\[ S_L=A\cup B,\qquad S_\phi=A\cup(B-1), \]and consequently
\[ |S_\phi\cap[1,x]| \geq \tfrac12|S_L\cap[1,x]|-O(1). \tag{4.2} \]Ballot–Luca applied to the Lucas recurrence gives
\(\underline d(S_L)>0\), so (b) (4.2) proves
\(\underline d(S_\phi)>0\). This is also independently supported by Wang's 2026
prime-plus-Lucas theorem.
Together with Ding's current Theorem 1.2, this identifies \(\phi\) as an explicit base for
which both \(S_\phi\) and its complement have positive lower density.
Plastic constant
Let \(\rho\) be the real root of \(x^3-x-1\),
\(\rho=1.324717957244746\ldots\). The polynomial is irreducible by the rational-root
test. Its other two roots are complex conjugates whose squared modulus is \(1/\rho<1\).
Thus (a) \(\rho\) is a Pisot number and the theorem applies.
The exact trace sequence begins
\[ T_0=3,\quad T_1=0,\quad T_2=2,\qquad T_n=T_{n-2}+T_{n-3}\quad(n\geq3). \]Since the two non-real roots have modulus \(\rho^{-1/2}\),
\(|T_n-\rho^n|\leq2\rho^{-n/2}<1\) for \(n\geq5\).
Hence (a) \(\lfloor\rho^n\rfloor-T_n\in\{-1,0\}\) for every \(n\geq5\).
A degree-four Salem example
Let \(\sigma=1.722083805739042\ldots\) be the largest root of
\[ x^4-x^3-x^2-x+1. \]Dividing by \(x^2\) and writing \(y=x+x^{-1}\) gives
\[ y^2-y-3=0. \]One \(y\)-root is \(>2\), yielding the reciprocal real pair
\(\sigma,\sigma^{-1}\); the other lies in \((-2,2)\), yielding a conjugate pair
on the unit circle. A direct monic-quadratic factor check shows the quartic is
irreducible over \(\mathbb Q\). Thus (a) \(\sigma\) is a Salem number and the theorem
applies.
5. Standalone finite verification
The standalone verifier is
runs/erdos244_wave5o_verify.py.
It uses only the Python standard library and contains no downloaded tables.
Run:
python3 runs/erdos244_wave5o_verify.py --limit 1000000 --algebraic-k 120
SHA-256 of the verifier used for this report:
39418feb2b985ea842847b098648fc918d20c756110e48aa098d8de76d5d56e0
It independently:
1. sieves the primes from scratch;
2. computes algebraic traces by Newton's identities with exact integers;
3. isolates each real algebraic root by Decimal bisection;
4. recomputes every floor at 100-digit and 180-digit precision and requires agreement;
5. verifies (4.1) through \(k=120\);
6. constructs the representation bitsets through \(10^6\);
7. checks \(2|S_\phi\cap[1,x]|\geq|S_L\cap[1,x]|\) at every one of the
\(10^6\) prefixes.
The core exact routines are:
def newton_power_sums(coefficients, K):
d, c = len(coefficients) - 1, coefficients[1:]
p = [d]
for k in range(1, K + 1):
if k <= d:
total = sum(c[j - 1] * p[k - j] for j in range(1, k))
total += k * c[k - 1]
else:
total = sum(c[j - 1] * p[k - j] for j in range(1, d + 1))
p.append(-total)
return p
def representation_mask(N, primes, shifts):
represented = bytearray(N + 1)
for shift in set(shifts):
for prime in primes:
if prime + shift > N:
break
represented[prime + shift] = 1
return represented
Exact finite output
(d) The correction sets observed for \(0\leq k\leq120\), after independent
100/180-digit agreement, were:
golden ratio: {-1, 0}
plastic constant: {-2, -1, 0, 1} (the extra values occur only in the initial terms)
degree-4 Salem: {-3, -2, -1, 0, 1}
(d) Exact counts of representable integers were:
| base | \(x\) | \(|S_C\cap[1,x]|\) | proportion |
|---|---:|---:|---:|
| golden ratio | 1,000 | 919 | 0.919000 |
| golden ratio | 10,000 | 8,925 | 0.892500 |
| golden ratio | 100,000 | 88,061 | 0.880610 |
| golden ratio | 1,000,000 | 869,757 | 0.869757 |
| plastic constant | 1,000 | 985 | 0.985000 |
| plastic constant | 10,000 | 9,837 | 0.983700 |
| plastic constant | 100,000 | 98,047 | 0.980470 |
| plastic constant | 1,000,000 | 979,621 | 0.979621 |
| degree-4 Salem | 1,000 | 800 | 0.800000 |
| degree-4 Salem | 10,000 | 8,021 | 0.802100 |
| degree-4 Salem | 100,000 | 85,704 | 0.857040 |
| degree-4 Salem | 1,000,000 | 848,752 | 0.848752 |
(d) The minimum prefix proportions over \(10^5\leq x\leq10^6\) were:
golden ratio: 868538 / 998614 = 0.869743464442
plastic constant: 943885 / 963569 = 0.979571779499
degree-4 Salem: 848571 / 999791 = 0.848748388413
(d) At \(x=10^6\), the independently generated Lucas sumset had 886,650 elements,
and
\[ 2|S_\phi\cap[1,10^6]|-|S_L\cap[1,10^6]|=852864. \]The corresponding inequality passed for every integer prefix \(1\leq x\leq10^6\).
These finite proportions are not treated as estimates of a limiting natural density and
play no role in the asymptotic proof.
6. Exact remaining wall for arbitrary \(C\)
For
\[ W(n)=\prod_{p\mid n}\left(1+\frac1p\right), \]the standard Romanoff second-moment argument reduces the general problem to the following
pointwise pair-correlation estimate:
\[ \boxed{\quad \sum_{\substack{1\leq k<\ell\leq K\\ \lfloor C^k\rfloor\ne\lfloor C^\ell\rfloor}} W\!\left(\lfloor C^\ell\rfloor-\lfloor C^k\rfloor\right) =O_C(K^2) \quad(K\to\infty).\quad} \tag{6.1} \]- (b) The Selberg-sieve/second-moment machinery in Romanoff's method shows that
(6.1) is sufficient for positive lower density.
- (b) Ding proves a sharper asymptotic version of (6.1) for almost every \(C\),
with leading constant \(\zeta(2)/(2\zeta(4))\), by integrating over \(C\) and using
Borel–Cantelli.
- (c) That metric proof does not provide (6.1) for a specified exceptional
\(C\). Tao's residue-concentration comment identifies exactly how (6.1) could fail:
too many exponents could collide in one residue class for many moduli.
- (a) The trace argument above bypasses (6.1) only when
\(\lfloor C^{mn}\rfloor\) stays within a fixed finite set of shifts of an integral
recurrence. For a general rational, algebraic, or transcendental \(C\), there is no
such bounded trace error.
A finite computation of (6.1) through any \(K\) cannot supply the required all-\(K\)
bound. Computing the raw \(K(K-1)/2\) differences is only quadratic in \(K\), but exact
factorisation of exponentially large differences rapidly becomes the dominant cost; more
importantly, no finite cutoff controls later residue concentration. The missing ingredient
is therefore a pointwise, all-scale residue/correlation lemma, not a larger finite search.
7. Verified outcome
The full every-real-\(C\) problem remains open. The concrete progress is a rigorous
affirmative result for the entire explicit class of Pisot and Salem bases, obtained by a
finite-perturbation reduction to Ballot–Luca's linear-recurrence theorem, plus an exact
finite verifier and representation tables for three nonintegral bases.
PARTIAL: Positive lower density is proved for every Pisot or Salem base C (rigorous modulo Ballot–Luca), while arbitrary real C still requires the pointwise Romanoff correlation bound (6.1).