ERDŐS/DAILY ▸

← back to the ledger

ERDőS #244 · PARTIAL

Erdős problem 244 — live-page audit, explicit algebraic bases, and verification

Access/research date: 2026-07-26 (UTC).

Claim labels used below:

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:

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:

Int. Közl. 6 (1961), 221–254; the problem is item (14) on p. 230.

Math. Ann. 109 (1934), 668–678.

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.

many candidate exceptions, this problem has uncountably many possible exceptional bases, making a pointwise elimination ambitious.

\(\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 Hungarian Academy repository. 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.

\[ \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.

\(\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, DOI 10.4064/aa161-1-3.

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.

  1. (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.

  1. (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.

  1. (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 ratio1,0009190.919000
golden ratio10,0008,9250.892500
golden ratio100,00088,0610.880610
golden ratio1,000,000869,7570.869757
plastic constant1,0009850.985000
plastic constant10,0009,8370.983700
plastic constant100,00098,0470.980470
plastic constant1,000,000979,6210.979621
degree-4 Salem1,0008000.800000
degree-4 Salem10,0008,0210.802100
degree-4 Salem100,00085,7040.857040
degree-4 Salem1,000,000848,7520.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} \]

(6.1) is sufficient for positive lower density.

with leading constant \(\zeta(2)/(2\zeta(4))\), by integrating over \(C\) and using Borel–Cantelli.

\(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.

\(\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).

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger