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<p_u\) be primes and let \(k\geq 1\). Let \(F_k(p_1,\ldots,p_u)\) be such that every interval of \(k\) positive integers contains at least \(F_k(p_1,\ldots,p_u)\) multiples of at least one of the \(p_i\).

Estimate \(F_k(p_1,\ldots,p_u)\), particularly in the range \(k=\alpha p_u\) for constant \(\alpha>2\).

Status and stop-condition audit

The rendered page says OPEN, was last edited 23 January 2026, and displayed all of the following on 2026-07-27: (d)

• 6 comments;
• 0 claimed proofs;
• Likes: None;
• Interested in collaborating: None;
• Currently working on this problem: None;
• difficult/tractable/formalisable/formalisation-work markers: all None;
• “Formalised statement? No.”

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 [Va99] as Various, Some of Paul's 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.

All six comments

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

1. Nat Sothanaphan replied that a check found minor issues and that the

connection was already Green--Ruzsa, Proposition 4.1.

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

1. Chojecki acknowledged that observation.
2. Woett pointed to [Er78, p. 35], [Er86c, p. 60], and problem 650.
3. 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.

Interpretation used here

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

1. Primary-source audit

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<p_{k^2-1}\), Erdős reports with Selfridge 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)

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

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

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

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

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

2. Uniform elementary lower bound

Let \(P=p_u\).

Theorem

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)

Proof

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

3. Why the bound is sharp for every \(u\) when \(2<\alpha<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

Rectangular prime-grid lemma

For fixed \(a,b\), there are arbitrarily large grids of distinct primes

with \(d_0=0\), in which \(\max p_{r,c}/\min p_{r,c}\to1\). (b)

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:

• \(L\geq2P\);
• \(L\leq3q_0-1\), the length of (10);
• all the row and column points lie in (10);
• the points in (9), whose total span is \(P+1\), fit inside a length-\(L\)

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):

The minimum is attained by arbitrarily large prime tuples. (b)

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)

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

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

If \(L=qM+r\), \(0\leq r<M\), periodicity gives the exact formula

Thus one complete cyclic scan is exhaustive; a minimizing residue can always be shifted by \(M\) to produce a positive interval. (a)

The standalone scanner applies (12) to the prefixes of the primes through

1. The resulting exact minima are: (d)

The largest period scanned is

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

This implication is elementary. (a)

For \(r=3\), Katz--Tao's three-slope inequality gives

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

therefore isolates the corresponding inverse-exponent gap between

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)\),

uniformly in the prime tuple. (b) Equivalently, by increasing the allowed threshold \(r_0\), the exponent can be made arbitrarily close from below to

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.