Erdős problem 1143 — live-page audit, sharp \(2<\alpha<3\) reconstruction, and exact finite computations
Accessed 2026-07-27 UTC. Labels used below are:
- (a) elementary-rigorous;
- (b) rigorous modulo a named theorem;
- (c) plausible/structural-unverified;
- (d) computational-only.
0. Mandatory live-page check
I fetched the rendered page and its full discussion through the Bright Data
residential-browser path:
- <https://www.erdosproblems.com/1143>
- <https://www.erdosproblems.com/forum/discuss/1143> (redirecting to
/forum/thread/1143)
The direct selector extraction was initially clipped, so I separately extracted
the complete rendered body.innerText, the comment-thread text, all thread
links, and a full-page screenshot.
Verbatim current statement
> Let \(p_1<\cdots > > Estimate \(F_k(p_1,\ldots,p_u)\), particularly in the range \(k=\alpha p_u\) for constant \(\alpha>2\). The rendered page says OPEN, was last edited 23 January 2026, and displayed all of the following on 2026-07-27: (d) Thus no mandatory stop condition applied. The page's only stated result is: > In [Va99] it is reported that Erdős and Selfridge found 'the exact bound' > when \(2<\alpha<3\), and that 'if \(\alpha>3\) then very little is known'. > No reference is given, and I cannot find a relevant paper of Erdős and > Selfridge. The live bibliography widget identifies favorite problems*, a booklet for the 1999 Budapest conference “Paul Erdős and his mathematics.” The page also points to problem 970, the Jacobsthal-function problem. The thread itself warns that comments are unverified. In condensed form: 1. Przemek Chojecki (29 April 2026) linked a draft note asserting a connection with inverse arithmetic Kakeya and problem 1097, including \(F_{\lfloor\alpha p_u\rfloor}\gg u^{6/11}\) for \(\alpha\geq3\). 2. Nat Sothanaphan replied that a check found minor issues and that the connection was already Green--Ruzsa, Proposition 4.1. 3. Thomas Bloom confirmed that it is one of Green--Ruzsa's arithmetic-Kakeya equivalences and said that their references clarify the Erdős--Selfridge attribution. 4. Chojecki acknowledged that observation. 5. Woett pointed to 6. Adenwalla asked whether “multiples of at least one” means the union of all covered integers, or instead many multiples of a single chosen prime. There was no hidden proof claim or worker marker in the thread. I use the distinct-union interpretation where \(I\) runs over intervals of \(L\) consecutive positive integers. This is not guessed from the ambiguous English: it is exactly the definition in Ruzsa's 1995 primary source and in the linked 2026 draft. (b) The page leaves rounding in \(L=\alpha p_u\) implicit. Whenever it matters below I write an integer \(L\), or explicitly take \(L=\lfloor\alpha p_u\rfloor\). The following sources were opened and their relevant pages or propositions checked. 1. Erdős 1978. P. Erdős, *Problems and results in combinatorial analysis and combinatorial number theory*, Congressus Numerantium XXI (1978), 29--40, §6, pp. 35--38: <https://users.renyi.hu/~p_erdos/1978-36.pdf>. For \(k^2\) primes \(p_0<\cdots that every interval longer than \(2p_{k^2-1}\) has at least \(2k\) covered integers, and constructs prime tuples and intervals almost \(3p_{k^2-1}\) long with exactly \(2k\). The proof uses the multiplicity, powers-of-two, prime-pattern, and CRT arguments reconstructed below. (b) 2. Ruzsa 1995. I. Z. Ruzsa, Few multiples of many primes, Studia Sci. Math. Hungar. 30 (1995), 123--125: <https://real-j.mtak.hu/5473/1/StudScientMath_30.pdf>. The paper defines (1), attributes the sharp \(2p_u\) lower bound and near-\(3p_u\) examples to Erdős--Selfridge, and proves that, for fixed \(\rho\geq3\) and \(r=\lfloor\rho\rfloor\), there are \(u\)-prime tuples with \[
F_{\rho p_u}\ll_\rho (u\log u)^{1-1/r}.
\] Ruzsa explicitly says that his argument did not show infinitely many such tuples. (b) 3. Green--Ruzsa 2017/2019. B. Green and I. Ruzsa, On the arithmetic Kakeya conjecture of Katz and Tao, <https://arxiv.org/abs/1712.02108>. Proposition 4.1 proves, for integer \(r\), that \[
K_r(u)\leq G_r(u)\leq rK_r(u), \tag{2}
\] where \(K_r(u)\) is the smallest size of an integer set containing \(r\)-term APs with \(u\) distinct common differences, and \(G_r(u)\) is the minimum of \(F_{rp_u}\) over prime tuples. Their Theorem 1.1 makes the corresponding asymptotic statement equivalent to arithmetic Kakeya. (b) 4. Katz--Tao bounds. N. Katz and T. Tao, A new bound on partial sum-sets and difference-sets, <https://arxiv.org/abs/math/9906097>, prove the exponents \(11/6\) for three input slopes and \(7/4\) when a fourth slope is controlled. Their later New bounds on Kakeya problems, <https://arxiv.org/abs/math/0102135>, supplies the best currently known unrestricted finite-slope exponent \[
\beta_0=1.67513\ldots,
\qquad \beta_0^3-4\beta_0+2=0.
\] Tao's 2025 paper <https://arxiv.org/abs/2511.15135>, §1.1, explicitly confirms that \(\inf_R\mathrm{SD}(R;-1)\leq\beta_0\) remains the current record. (b) 5. The April 2026 draft. <https://www.ulam.ai/research/erdos1143-partial.pdf> proves in its stated notation a real-\(\alpha\) transfer and records the consequences \(u^{6/11}\) for \(\alpha\geq3\) and \(u^{4/7}\) for \(\alpha\geq7\). Because it is a draft, and the thread itself reports minor check issues, I do not use it as the sole support for any theorem. Its integer-\(\alpha\) core is already Green--Ruzsa Proposition 4.1. 6. Other comment references. The cited page 60 of Erdős's 1986 note <https://users.renyi.hu/~p_erdos/1986-15.pdf> discusses related “complete sequences” and Jacobsthal-type questions; it does not contain a solution for \(\alpha>3\). The 2020 paper <https://arxiv.org/abs/2011.07056> and the 2024 paper <https://arxiv.org/abs/2411.13395> concern related/generalized arithmetic Kakeya pattern problems, not a closed estimate for (1). I found no primary source claiming that problem 1143 is solved. That is a search report, not a proof that no uncatalogued paper exists. (c) Let \(P=p_u\). For every \(u\)-tuple of distinct primes and every integer \(L\geq2P\), This is the Erdős--Selfridge multiplicity argument, written for arbitrary \(u\), including all ceiling and endpoint details. (a) Take any interval \(I\) of \(L\) consecutive integers and split it into its first \(h=\lfloor L/2\rfloor\) integers \(I_1\) and its remaining \ell=\lceil L/2\rceil\) integers \(I_2\). Both lengths are at least \(P\). Thus \(I_1\) contains a multiple of every \(p_i\). For \(x\in I_1\), let \(\nu(x)\) be the number of selected primes dividing \(x\), and let Counting prime divisibilities in \(I_1\) gives Choose \(m\in I_1\) divisible by \(n\) of the primes. Let \(B=\min I_2\). For each such prime \(p\), choose the least \(s\geq0\) for which Write \(I_1=[A,B-1]\) and \(I_2=[B,B+\ell-1]\), so \(h=B-A\leq\ell\). This point is in \(I_2\). Indeed, if \(s=0\), then If \(s>0\), minimality gives the left side is an integer, so it is at most \(B+\ell-1\). Unique factorisation makes the \(n\) offsets \(2^sp\) distinct, even when one selected prime is 2. Hence \(I_2\) contains \(n\) distinct covered points. Combining this with (4), Finally, since the largest product of two integers with sum \(m\) is \(\lfloor m^2/4\rfloor\). This proves (3). This section reconstructs the known “exact bound” rather than claiming it as new. The rectangular form makes the non-square cases and the actual CRT certificate explicit. Choose \(a\leq b\) with \(ab\geq u\) and For fixed \(a,b\), there are arbitrarily large grids of distinct primes Here is a direct PNT proof. In a dyadic interval \([X,2X]\), partition into subintervals of length \(H=(\log X)^{b+2}=o(X)\). The prime number theorem forces one subinterval to contain at least \(H/(3\log X)\) primes for all large \(X\). Divide its ordered primes into disjoint blocks of \(b\). There are at least \(H/(4b\log X)\) blocks. Their disjoint diameters sum to at most \(H\), so fewer than \(H/(8b\log X)\) have diameter exceeding \(8b\log X\). At least \(H/(8b\log X)\) good blocks remain. There are at most \((8b\log X+1)^{b-1}\) normalised difference patterns for a good block, while Pigeonholing therefore gives \(a\) blocks with the same pattern. Their first primes are the \(q_r\), and the common offsets are the \(d_c\). Select \(u\) cells of the \(a\times b\) grid that meet every row and column and include the top-right cell. This is possible because \(\max(a,b)\leq u\leq ab\). Put \(q_0=\min q_r\), and use CRT to choose \(x\) satisfying, for every selected cell, Then the two consecutive multiples of \(p_{r,c}\) depend only on its row and its column. The preceding multiple is at most \(x-q_0\), while the following multiple is at least \(x+2q_0\). Therefore the safe interval contains exactly the \(a+b\) row/column points and no other selected-prime multiples. Let \(P\) be the top-right prime and \(L=\lfloor\alpha P\rfloor\). Because the grid can be made arbitrarily tight, for fixed \(2<\alpha<3\) and a sufficiently large grid: subinterval of (10). Shift \(x\) by a multiple of \(\prod p_{r,c}\) to make that interval positive. It has exactly \(a+b=\lceil2\sqrt u\rceil\) covered integers. With (3):Status and stop-condition audit
[Va99] as *Various, Some of Paul'sAll six comments
[Er78, p. 35], [Er86c, p. 60], and problem 650.Interpretation used here
1. Primary-source audit
2. Uniform elementary lower bound
Theorem
Proof
3. Why the bound is sharp for every \(u\) when \(2<\alpha<3\)
Rectangular prime-grid lemma
Equation (11) is a worst-prime-tuple statement. It does not say that every
fixed tuple has that value; the finite table below shows how much larger
fixed dense tuples can be.
4. Explicit \(\alpha=5/2\) CRT certificates
The verifier starts from the concrete prime grid (d)
\[ \begin{array}{rrrr} 5101&5107&5113&5119\\ 5381&5387&5393&5399\\ 5431&5437&5443&5449\\ 5641&5647&5653&5659 \end{array} \]whose row bases are \(5101,5381,5431,5641\) and whose offsets are
\(0,6,12,18\). Trial division is redone from scratch. For each
\(1\leq u\leq16\), the code selects cells in an optimal rectangle, solves
(8), lists every multiple of every selected prime in the witness interval,
and checks (3)--(6).
| \(u\) | rectangle | \(p_u\) | \(L=\lfloor5p_u/2\rfloor\) | exact \(F_L\) |
|---:|:---:|---:|---:|---:|
| 1 | \(1\times1\) | 5101 | 12752 | 2 |
| 2 | \(1\times2\) | 5107 | 12767 | 3 |
| 3 | \(2\times2\) | 5387 | 13467 | 4 |
| 4 | \(2\times2\) | 5387 | 13467 | 4 |
| 5 | \(2\times3\) | 5393 | 13482 | 5 |
| 6 | \(2\times3\) | 5393 | 13482 | 5 |
| 7 | \(3\times3\) | 5443 | 13607 | 6 |
| 8 | \(3\times3\) | 5443 | 13607 | 6 |
| 9 | \(3\times3\) | 5443 | 13607 | 6 |
| 10 | \(3\times4\) | 5449 | 13622 | 7 |
| 11 | \(3\times4\) | 5449 | 13622 | 7 |
| 12 | \(3\times4\) | 5449 | 13622 | 7 |
| 13 | \(4\times4\) | 5659 | 14147 | 8 |
| 14 | \(4\times4\) | 5659 | 14147 | 8 |
| 15 | \(4\times4\) | 5659 | 14147 | 8 |
| 16 | \(4\times4\) | 5659 | 14147 | 8 |
These are finite computational certificates plus the elementary universal
lower bound, so each displayed equality is (a)+(d).
5. Exact finite-period reduction for a fixed tuple
For a fixed tuple set
\[ M=\prod_{i=1}^u p_i,\qquad h(n)=\mathbf1_{\{\exists i:p_i\mid n\}},\qquad C=\sum_{n=0}^{M-1}h(n)=M-\varphi(M). \]If \(L=qM+r\), \(0\leq r
be shifted by \(M\) to produce a positive interval. (a)
The standalone scanner applies (12) to the prefixes of the primes through
19. The resulting exact minima are: (d)
| \(u\) | primes | \(2P+1\) | \(\lfloor5P/2\rfloor\) | \(3P\) | \(4P\) | \(5P\) | \(6P\) | \(8P\) | \(10P\) |
|---:|:---|---:|---:|---:|---:|---:|---:|---:|---:|
| 1 | 2 | 2 | 2 | 3 | 4 | 5 | 6 | 8 | 10 |
| 2 | 2,3 | 4 | 4 | 5 | 8 | 9 | 12 | 16 | 20 |
| 3 | 2,3,5 | 7 | 8 | 10 | 14 | 17 | 22 | 28 | 36 |
| 4 | 2,3,5,7 | 10 | 11 | 14 | 20 | 25 | 31 | 42 | 52 |
| 5 | 2,3,5,7,11 | 16 | 19 | 23 | 32 | 41 | 50 | 67 | 84 |
| 6 | 2,3,5,7,11,13 | 19 | 23 | 28 | 38 | 49 | 59 | 80 | 102 |
| 7 | 2,3,5,7,11,13,17 | 25 | 31 | 37 | 51 | 64 | 78 | 107 | 133 |
| 8 | 2,3,5,7,11,13,17,19 | 28 | 35 | 42 | 58 | 72 | 89 | 120 | 149 |
The largest period scanned is
\[ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 =9\,699\,690. \]The code hard-codes neither the coverage arrays nor the proof witnesses. It
rebuilds each bytearray by divisibility, scans every cyclic start, checks the
first minimizing residue against regression constants, directly recounts
the positive witness interval, and uses a separate nested-loop exhaustive
oracle for all periods at most 2310.
6. What the arithmetic-Kakeya machinery gives now
Let \(r\geq3\). Any interval of length at least \(rP\) supplies an \(r\)-term
AP of covered points with common difference \(p_i\), for every \(i\).
Consequently
\[ F_L(p_1,\ldots,p_u)\geq K_r(u) \qquad(L\geq rP). \tag{13} \]This implication is elementary. (a)
For \(r=3\), Katz--Tao's three-slope inequality gives
\[ F_L(p_1,\ldots,p_u)\gg u^{6/11} \qquad(L\geq3P). \tag{14} \]The explicit projective map \(t\mapsto2/(t+1)\) sends the input slopes
\(\{0,1,\infty\}\) to the AP positions \(\{2,1,0\}\) and the output slope
\(-1\) to \(\infty\). Thus (14) is rigorous modulo Katz--Tao, independently
of the 2026 draft. (b)
For the worst-prime-tuple quantity at exactly \(3P\), (2) says that its
growth is, up to a factor 3, precisely the inverse of the maximum number of
3-AP differences in an \(m\)-element set. The present sum-difference
exponent interval
\[ 1.77898\ldots\leq\gamma_3\leq11/6 \]therefore isolates the corresponding inverse-exponent gap between
\[ 6/11=0.54545\ldots \quad\hbox{and}\quad 1/1.77898\ldots=0.56212\ldots, \tag{15} \]with the upper-side construction understood along its certified family of
sizes. (b)
There is also a useful large-\(\alpha\) consequence not stated in the live
page. Given any finite rational slope set, a projective transformation can
send its output slope to \(\infty\), after which an affine rational scaling
places all input slopes in \(\{0,\ldots,r_0-1\}\) for some finite \(r_0\).
If an \(m\)-element set \(A\) contains APs with distinct differences in a
set \(D\), choose one start \(a_d\) for each \(d\in D\) and put
\(E=\{(a_d,d):d\in D\}\). Every input projection of \(E\) lies in \(A\),
whereas its \(\infty\)-projection is \(D\). The sum-difference inequality
therefore bounds \(\#D\) by a power of \(m\).
Combining this observation with the Katz--Tao record \(\beta_0\) shows:
for every \(\varepsilon>0\), there is an integer \(r_0(\varepsilon)\) such
that, for every \(\alpha\geq r_0(\varepsilon)\),
\[ F_{\lfloor\alpha P\rfloor}(p_1,\ldots,p_u) \gg_\varepsilon u^{1/(\beta_0+\varepsilon)} \]uniformly in the prime tuple. (b) Equivalently, by increasing the
allowed threshold \(r_0\), the exponent can be made arbitrarily close from
below to
\[ 1/\beta_0=0.596968\ldots. \]This improves the four-slope \(u^{4/7}\) exponent for sufficiently large
fixed \(\alpha\), but it gives no small numerical threshold \(r_0\) and is
far from the conjectural near-linear exponent.
7. Exact wall and computation cost
Nothing here closes \(\alpha\geq3\). The missing lemma is now precise:
one needs stronger uniform bounds on the number of distinct \(r\)-term-AP
differences supported by an \(m\)-element integer set (equivalently,
stronger finite-slope sum-difference inequalities). In the large-\(r\)
limit, obtaining exponents tending to 1 is the arithmetic Kakeya
conjecture. A fixed-\(u\) or computational list does not provide the
uniformity in \(u\) needed for that step.
The direct exact method also meets a concrete primorial wall. The verifier's
full run took 13.77 seconds. Extending the same eight-window scan to the
next prefix would use period \(223\,092\,870\), about 223 MB and an
extrapolated \(0.09\) core-hours (roughly five minutes). Through prime 29
the period is \(6\,469\,693\,230\), requiring about 6.5 GB and an extrapolated
\(2.5\) core-hours. At a representative USD 0.06 per vCPU-hour the latter
is about USD 0.15 of raw CPU, but a larger-memory VM is required. Neither
extension was run under the stated few-CPU-minute limit. (c)
8. Reproduction
The standalone, standard-library-only verifier is
runs/erdos1143_wave6v_reverify.py. Run:
python runs/erdos1143_wave6v_reverify.py
The reference run ended with:
8 2,3,5,7,11,13,17,19 28 35 42 58 72 89 120 149
ALL CHECKS PASSED in 13.77 seconds
PARTIAL: Reconstructed the known sharp worst-prime-tuple value \(\lceil2\sqrt u\rceil\) for \(2<\alpha<3\), certified explicit \(\alpha=5/2\) examples for \(u\leq16\), proved current arithmetic-Kakeya lower transfers, and exhaustively computed fixed-prefix tables through \(u=8\); \(\alpha\geq3\) remains open.