GPT 6 Astra Ultra attempt on Math-5380

FORMAL RESTATEMENT

Erdős #29; reconstruction, 2026-09-23. Here $\mathbb N_0=\{0,1,\ldots\}$. Construct explicitly $A\subseteq\mathbb N_0$ such that $A+A=\mathbb N_0$ and the ordered representation function \[ r_A(n)=|\{(a,a')\in A^2:a+a'=n\}| \] satisfies $r_A(n)=o(n^\epsilon)$ for every $\epsilon>0$. We give a membership rule computable in time polynomial in the number of binary digits of its input and prove $r_A(n)=n^{o(1)}$.

QUICK LITERATURE AND CONTEXT CHECK

The problem is marked proved on its current page. Jain, Pham, Sawhney and Zakharov gave an explicit construction in An explicit economical additive basis $2024$, using a modular construction of Ruzsa and mixed radix expansions. We reconstruct that method, including the finite-field calculation behind the modular cover. The proof uses the standard prime number theorem in the fixed progression $3$ modulo $8$ only to control the sizes of the primes and the membership running time. Neither the construction nor the conclusion is claimed as new.

WORK

1. A modular basis with a uniform representation bound

Let $p>12$ be a prime with $p\equiv3\pmod8$, so $2$ is a quadratic nonresidue modulo $p$. For $c\in\{3,4,6\}$ and $0\leq x<p$ define \[ f_c(x)=x+2p\,[cx^2]_p,\qquad D_p=\{f_c(x):c\in\{3,4,6\},\ 0\leq x<p\}, \] where $[z]_p$ is the representative in $\{0,\ldots,p-1\}$. Let $D'_p=D_p+\{-p,0\}$ and let $E_p$ be its image modulo $p^2$, represented by integers from $0$ to $p^2-1$. We prove that for every residue $n$, \[ 1\leq r_{E_p}(n\bmod p^2)\leq M,\qquad M=432. \tag{1} \] In particular $0\in E_p$.

For coverage, write $0\leq n<p^2$ as $n=r+pq$, with $0\leq r,q<p$, and put $t=q/2$ in $\mathbb F_p$. We seek $x+y=r$ and $cx^2+dy^2=t$ in that field. Eliminating $y$ gives a quadratic in $x$ whose discriminant is \[ 4\big((c+d)t-cd r^2\big). \] The choices $(c,d)=(3,6)$ and $(4,4)$ give respectively $36(t-2r^2)$ and $32(t-2r^2)$. If $t-2r^2=0$ both quadratics have a root. Otherwise the quotient of the discriminants is $8/9$, a quadratic nonresidue, so precisely one discriminant is a square. The leading coefficients $9$ and $8$ are nonzero modulo $p$. Hence one of the two equations has a solution.

Choose representatives $x,y$ in $[0,p-1]$. Then $x+y=r+ep$ for some $e\in\{0,1\}$, and \[ f_c(x)+f_d(y)\equiv n+ep\pmod{p^2}. \] Subtracting $ep$ from the first summand is allowed in $D'_p$, so every residue is a sum of two elements of $E_p$.

For the upper bound, fix an integer $v$. In a representation $v=f_c(x)+f_d(y)$, the value $s=x+y$ is uniquely specified by $s\equiv v\pmod{2p}$ and $0\leq s\leq2p-2$, if it exists at all. The congruence \[ cx^2+d(s-x)^2\equiv\frac{v-s}{2p}\pmod p \] has at most two roots for each ordered pair $(c,d)$: its leading coefficient $c+d$ is between $6$ and $12$, and is nonzero modulo $p$. Thus the number of ordered representations in $D_p$ is at most $18$. There may be duplicate descriptions of an element by $(c,x)$; counting all descriptions only increases this upper bound.

The two possible shifts for each summand imply $r_{D'_p}(v)\leq72$. As $D'_p\subset[-p,2p^2)$, its pair sums lie in $[-2p,4p^2)$. There are at most six integers in this interval with any fixed residue modulo $p^2$. Choose one lift in $D'_p$ for each element of $E_p$; this injects ordered residue representations into these integer representations. The bound $6\cdot72=432$ proves $1$.

2. The explicit mixed radix set

Let $p_i$ be the least prime congruent to $3$ modulo $8$ with $p_i\geq i+13$, and put $b_i=p_i^2$. Repeated primes are permitted; the bases are nondecreasing. The prime number theorem for this fixed arithmetic progression gives $p_i=O(i+13)$, whereas $p_i\geq i+13$ holds by construction. Let $E_i=E_{p_i}$ and $Q_i=\prod_{j<i}b_j$, with $Q_1=1$.

Every nonnegative integer has a canonical finite expansion $a=\sum_{i=1}^{\ell}a_iQ_i$, with $0\leq a_i<b_i$ and nonzero top digit unless $a=0$. Define $A$ by requiring \[ a_i\in E_i\quad(1\leq i<\ell), \qquad 0\leq a_\ell<b_\ell, \tag{2} \] and include $0$. Thus the top digit is unrestricted, while every lower digit comes from its modular basis. Since $0\in E_i$, allowing leading zeros gives the same set as the canonical rule.

3. Every integer is represented, with carries checked

For $n>0$, write its digits as $n_1,\ldots,n_k$ with $n_k\geq1$. Start with carry $c_0=0$. For $i<k$, use $1$ to choose $a_i,a'_i\in E_i$ satisfying \[ a_i+a'_i+c_{i-1}\equiv n_i\pmod{b_i}. \] The next carry is the integer determined by \[ a_i+a'_i+c_{i-1}=n_i+c_i b_i. \] It belongs to $\{0,1\}$ because the left side is between $0$ and $2b_i-1$. Set $a_k=n_k-c_{k-1}\geq0$ and $a'_k=0$. This satisfies the top equality with no further carry. Both resulting integers satisfy $2$, even if a top digit vanishes, and their sum is exactly $n$. For $n=0$, use $0+0$. Therefore $A+A=\mathbb N_0$.

4. Bounding all representations, not only the constructed one

For a fixed $n$ of digit length $k$, orient a representation so that the smaller digit length of its two summands is $\ell\leq k$. Treat zero as having length one. The orientation costs a factor at most two. At each level $i<\ell$, both digits are restricted by $2$ and the incoming carry is already determined. There are at most $M$ ordered choices, by $1$. At level $\ell$ choose the top digit of the shorter summand in at most $b_\ell$ ways. Its lower digits and hence that entire summand are then fixed; the other summand is forced to be $n-a$. We have therefore bounded every representation by \[ r_A(n)\leq2\sum_{\ell=1}^k b_\ell M^{\ell-1} \leq2b_k M^k. \tag{3} \] Since $b_i\geq(i+13)^2$, a $k$-digit positive integer satisfies \[ \log n\geq\sum_{i<k}2\log(i+13)\gg k\log k. \] Thus $k=O(\log n/\log\log n)$; also $b_k=O((k+13)^2)$. Taking logarithms in $3$ yields \[ r_A(n)\leq\exp\!\left(O\!\left(\frac{\log n}{\log\log n}\right)\right) =n^{o(1)}. \] For any prescribed $\epsilon>0$, the exponent is eventually below $\epsilon/2$, so $r_A(n)/n^\epsilon\to0$, as required.

5. Why the construction is explicit

For an input of bit length $L$, at most $L$ bases need to be generated. The required primes have size $O(L+13)$, so even trial division and a sequential search in the progression find them in time polynomial in $L$. Every set $E_i$ is given by the displayed three quadratic formulas and two shifts and has a list of length $O(p_i)$. Repeated division finds the mixed radix digits, after which the finitely many membership tests in $2$ take polynomial time in $L$. This establishes the usual strong meaning of explicitness, rather than just an unbounded search through infinite candidate sets. $\square$

VERIFICATION AND LIMITS

The batch script checks $1$ exhaustively for $p=19,43,59$, checks the two-discriminant coverage argument in each of these fields, and tests the mixed radix membership and carry construction for all $n\leq5000$. These finite tests support the calculation; the arguments above prove the assertions for all permitted primes and all integers. The uniform constant $432$ is deliberately loose. No optimization or improvement of the published result is claimed. The fixed-progression prime-size estimate is the standard external number-theoretic input; the finite modular and mixed radix arguments are proved here.

FINAL STATUS

SOLVED (known affirmative construction reconstructed). The write-up provides a complete construction and proof with the explicitly stated prime-distribution theorem as an input. It does not claim novelty or an independent audit of the formal proof reported on the problem page.

SOURCES

https://www.erdosproblems.com/29. V. Jain, H. T. Pham, M. Sawhney and D. Zakharov, An explicit economical additive basis, especially Section 2 and its Ruzsa construction: https://arxiv.org/abs/2405.08650. Checked 2026-09-23. Checks are in verification/solved_batch_26_checks.py.

This measures completion of the reconstruction using the stated classical prime-distribution input, not originality.

COMPLETION ESTIMATE

COMPLETION: 100%