ERDŐS/DAILY ▸

← back to the ledger

ERDőS #849 · PARTIAL

Erdős problem #849 — live audit, literature audit, and an exact triangular-slice computation

Date of audit and computation: 2026-07-27 (UTC).

Claim labels used below:

and linked;

as a theorem;

and verifier specified.

0. Mandatory live-page audit before doing mathematics

I fetched the live page through the configured

Bright Data browser on 2026-07-27, then separately fetched its

LaTeX-source view. Direct datacenter HTTP was

not used as authority.

The page's verbatim current statement is:

> Is it true that, for every integer \(t\geq 1\), there is some integer \(a\) such that

> \[ > \binom{n}{k}=a > \]

> (with \(1\leq k\leq n/2\)) has exactly \(t\) solutions?

The live state was OPEN. The full marker audit was:

and A182237.

Thus none of the mandated stop conditions applied.

The mathematical notes on the live page say, in substance and with the displayed

formulae transcribed exactly:

called Singmaster's conjecture.

for \(t\geq5\).

and believed that an absolute upper bound exists.

half-triangle when

\[ k\geq \exp((\log n)^{2/3+\epsilon}), \]

for \(a\) sufficiently large depending on \(\epsilon>0\).

The page cites:

Analytic Number Theory, Vol. 1 (1996), 333–335,

DOI 10.1007/978-1-4612-4086-0_18;

Singmaster's conjecture in the interior of Pascal's triangle,

Q. J. Math. 73 (2022), 1137–1177,

DOI 10.1093/qmath/haac006.

1. Convention and the easy exact cases

Write

\[ H(a)=\#\{(n,k):1\leq k\leq n/2,\ \binom nk=a\}. \]

This is the live page's half-triangle convention, not the usual convention that

counts both symmetric entries.

For every \(a\geq2\), \((a,1)\) is one solution. For fixed \(k\), the map

\(n\mapsto\binom nk\) is strictly increasing for \(n\geq k\). Hence different

solutions for a fixed \(a\) have different lower indices \(k\). Both statements

are (a).

The verifier independently enumerates all rows \(n\leq a\), stopping within a row

as soon as its increasing coefficients exceed \(a\). This is complete because

\(\binom nk\geq n\) for \(1\leq k\leq n/2\). It obtains **(d), with completeness

justified by (a)**:

| \(a\) | all half-triangle representations | \(H(a)\) |

|---:|---|---:|

| 2 | \((2,1)\) | 1 |

| 10 | \((5,2),(10,1)\) | 2 |

| 120 | \((10,3),(16,2),(120,1)\) | 3 |

| 3003 | \((14,6),(15,5),(78,2),(3003,1)\) | 4 |

Thus the live examples are exact, not merely lower bounds.

2. Primary-source literature audit

The following are the strongest directly relevant results I located.

1. Singmaster's original two-page note formulates bounded multiplicity and proves

\(O(\log a)\):

D. Singmaster, How often does an integer occur as a binomial coefficient?,

Amer. Math. Monthly 78 (1971), 385–386,

DOI 10.1080/00029890.1971.11992769.

2. Abbott–Erdős–Hanson prove average and normal order 2 in the full-triangle

convention and improve the worst-case bound to

\(O(\log a/\log\log a)\):

H. L. Abbott, P. Erdős, D. Hanson,

On the number of times an integer occurs as a binomial coefficient,

Amer. Math. Monthly 81 (1974), 256–261.

3. Kane's current best unconditional total bound is

\[ O\!\left(\frac{\log a\,\log\log\log a}{(\log\log a)^3}\right). \]

This is Theorem 1 of D. M. Kane,

Improved bounds on the number of ways of expressing \(t\) as a binomial coefficient,

INTEGERS 7 (2007), A53. This remains the best total bound according to the

2022 paper. (b)

4. Matomäki–Radziwiłł–Shao–Tao–Teräväinen prove Theorem 1.3: for fixed

\(0<\epsilon<1\) and sufficiently large \(a\), at most two half-triangle

representations lie in

\[ \exp((\log n)^{2/3+\epsilon})\leq k\leq n/2. \]

Their Remark 1.5 reduces the unbounded part to small \(k\), while Remark 1.7

warns that their effective constants are far too large for numerical

verification. Their Remark 1.5 also records that fixed pairs of lower indices

have only finitely many collisions via Siegel's theorem, but the resulting

growing cutoff is ineffective. (b)

5. A. Blokhuis, A. E. Brouwer, B. M. M. de Weger,

Binomial collisions and near collisions,

INTEGERS 17 (2017), A64, is the key finite-computation source. Its Theorem 1

states that all collisions are classified for

\[ (k,\ell)=(2,3),(2,4),(2,5),(2,6),(2,8),(3,4),(3,6),(4,6),(4,8), \]

and that no unknown collision exists with the larger row \(n\leq10^6\) or

collision value at most \(10^{60}\). The paper describes the exact modular

sieve used for the \(10^{60}\) computation and reports about 375 old-CPU hours.

(b)

I searched exact titles and combinations of “Singmaster”, “binomial collision”,

and “multiplicity” across arXiv and journal results, including 2023–2026 dates. I

found no peer-reviewed or arXiv primary source after the 2022 interior paper that

improves the total multiplicity bound or supplies a fifth half-triangle

representation. This is an honest search result, not a proof of absence. (c)

One 2026 ResearchGate/ISBN upload by R. Simonetto,

[*Conjecture de Singmaster … preuve de l'inexistence d'occurrences impaires

supérieures à 3*](https://www.researchgate.net/publication/400572247_Conjecture_de_Singmaster_sur_les_multiplicites_binomiales_dans_le_triangle_de_Pascal_et_preuve_de_l%27inexistence_d%27occurrences_impaires_superieures_a_3),

did appear in the search. It is not listed as a claimed proof on the live page.

Its displayed argument asserts that a central binomial coefficient has no

nontrivial collision and replaces \(\binom{2c}{c}\) by its Stirling asymptotic

\(4^c/\sqrt{\pi c}\) before a Lambert-\(W\) calculation. An asymptotic equality

cannot establish nonexistence of exact integral solutions; moreover, excluding

such central collisions is itself the missing Diophantine step. I therefore did

not use this upload as a theorem. Its claim concerns odd full-triangle

multiplicity and would not by itself settle the live page's \(t=5\) question

anyway.

3. New finite result: the entire \(k=2\) slice through row \(10^{32}\)

Theorem

Let \(4\leq n\leq10^{32}\) and put \(a=\binom n2\). Then

\[ H(a)= \begin{cases} 4,&n=78,\\ 3,&n\in\{16,21,56,120,153,221\},\\ 2,&\text{otherwise}. \end{cases} \]

The complete exceptional table is:

| \(n\) | \(a=\binom n2\) | representations other than \((a,1),(n,2)\) | \(H(a)\) |

|---:|---:|---|---:|

| 16 | 120 | \((10,3)\) | 3 |

| 21 | 210 | \((10,4)\) | 3 |

| 56 | 1540 | \((22,3)\) | 3 |

| 78 | 3003 | \((15,5),(14,6)\) | 4 |

| 120 | 7140 | \((36,3)\) | 3 |

| 153 | 11628 | \((19,5)\) | 3 |

| 221 | 24310 | \((17,8)\) | 3 |

This theorem is (b) overall: it combines the globally solved fixed pairs

\(\ell=3,4,5,6,8\) from Blokhuis–Brouwer–de Weger Theorem 1 with the new finite

exact computation for \(\ell=7\) and \(9\leq\ell\leq107\), which is (d).

Every displayed equality is independently recomputed with math.comb.

The largest value covered is

\[ \binom{10^{32}}2 =4999999999999999999999999999999950000000000000000000000000000000 <5\cdot10^{63}. \]

Thus, within the triangular \(k=2\) slice, this finite check goes about a factor

5000 beyond the \(10^{60}\) all-indices value threshold reported in the 2017

paper. This is deliberately not advertised as an all-indices extension.

Why the finite search is complete

Let

\[ A=\binom{10^{32}}2. \]

Suppose \(\binom n2=\binom m\ell\), with \(n\leq10^{32}\),

\(2<\ell\leq m/2\).

1. Finite lower-index range (a). For fixed \(\ell\),

\(\binom m\ell\) increases with \(m\), and its minimum in the half-triangle is

\(\binom{2\ell}{\ell}\). Exact integer comparison gives

\[ \binom{214}{107}\leq A<\binom{216}{108}. \]

Therefore only \(3\leq\ell\leq107\) can occur.

2. Exact row endpoint (a). For every untreated \(\ell\), binary search using

exact math.comb finds the unique \(m_{\max}\) satisfying

\[ \binom{m_{\max}}\ell\leq A< \binom{m_{\max}+1}\ell. \]

Every integer \(2\ell\leq m\leq m_{\max}\) is represented in the candidate

count below.

3. No-loss modular sieve (a). If \(B=\binom n2\), then

\[ 1+8B=(2n-1)^2. \tag{1} \]

For a prime \(p>\ell\), \(\ell!\) is invertible modulo \(p\), so

\(m\mapsto\binom m\ell\pmod p\) is a polynomial function depending only on

\(m\bmod p\). If

\(1+8\binom m\ell\) is a quadratic nonresidue modulo even one such \(p\),

(1) is impossible. Discarding that residue class therefore has no false

negatives.

4. Exact survivor decision (a). For every survivor the program computes

\(B=\binom m\ell\), \(D=1+8B\), and \(s=\lfloor\sqrt D\rfloor\) with arbitrary

precision. It accepts only if \(s^2=D\), \(s\) is odd, and the resulting

\(n=(1+s)/2\) obeys both \(n\leq10^{32}\) and

\(\binom n2=B\).

These four points show that the computational conclusion is exact, not

probabilistic. NumPy is used only to apply periodic Boolean masks; it never

evaluates a binomial coefficient or decides equality.

Reproducible run

Standalone verifier:

erdos849_wave7p_verify.py.

Run:

python3 -u runs/erdos849_wave7p_verify.py

Environment: Python 3.12.3, NumPy 2.4.4, Linux x86-64, Intel Xeon Platinum

8259CL. One core was used. Two clean full passes took 93.753 and 90.381 seconds

and produced the identical certificate hash below.

The verifier first performs a logically separate audit:

slices;

collisions and on untreated \(\ell=7,9\) ranges.

The full-run certificate was:

n_bound=100000000000000000000000000000000
max C(n,2)=4999999999999999999999999999999950000000000000000000000000000000
ell_max=107
searched_slices=100
total_candidates=4319058300
total_survivors=78419
unknown_hits=[]
certificate_sha256=58d9ab56135fdb811fcbdfa70385314c80ad5370dfda7b01486758831a5e7e19
VERIFIED

The dominant slices were:

| \(\ell\) | \(m_{\max}\) | candidates | exact survivors | hits |

|---:|---:|---:|---:|---:|

| 7 | 4,253,745,533 | 4,253,745,520 | 71,414 | 0 |

| 9 | 49,592,364 | 49,592,347 | 5,090 | 0 |

| 10 | 10,613,863 | 10,613,844 | 1,183 | 0 |

| 11 | 3,032,706 | 3,032,685 | 168 | 0 |

| 12 | 1,075,501 | 1,075,478 | 104 | 0 |

| 13–107 | — | 998,426 in aggregate | 460 in aggregate | 0 |

The aggregate row follows by subtraction from the recorded totals; the standalone

script recomputes every individual endpoint and includes all of them in the

certificate hash.

4. What this says about #849, and the exact remaining wall

The finite theorem does not produce \(t=5\) and does not settle the uniform

problem. Its direct consequence is:

> (b) If \(H(a)\geq5\) and \(a\) has a representation

> \(a=\binom n2\), then \(n>10^{32}\).

Equivalently, a \(t\geq5\) example below that triangular-row frontier must avoid

the entire \(k=2\) slice. This is a genuine but narrow exclusion.

The exact global obstruction is uniformity in the lower indices. A value with

\(H(a)\geq5\) needs at least four interior representations and hence a network

of binomial collisions among four distinct lower indices. For every fixed

pair \((k,\ell)\), Siegel-type arguments give finiteness, but they provide no

effective cutoff uniform as \(k,\ell\) grow. Matomäki et al. bound the number of

representations in the interior, but deliberately leave

\[ 2\leq k\leq \exp((\log n)^{2/3+\epsilon}) \]

as the edge region. The missing lemma would be an effective, uniform collision

theorem in that growing edge region—de Weger's conjectural classification of

all binomial collisions would be more than sufficient. No such lemma is

currently available in the cited sources.

Blindly enlarging this computation does not address that wall. In the triangular

slice the untreated \(\ell=7\) range dominates and grows as \(N^{2/7}\) when the

row bound is \(N\). Scaling from \(10^{32}\) to \(10^{40}\) would multiply this

run by about \(10^{16/7}\approx193\), or roughly 5 single-core hours on this VM

(about \$0.25–\$0.50 at a realistic \$0.05–\$0.10/core-hour). That would still

say nothing about candidates with no \(k=2\) representation. A useful next

computation would instead need a similarly exact, aggressively sieved joint

classification for the \(k=3\) and \(k=4\) slices beyond \(10^{60}\); the

dominant \((3,5)\) and \((4,5)\) families are substantially larger.

PARTIAL: Exact modulo the published fixed-pair theorem, every \(\binom n2\) with \(4\leq n\leq10^{32}\) has half-triangle multiplicity at most 4 (only \(n=78\) attains 4); a 4.319-billion-candidate exact sieve found no new \((2,\ell)\) collision, but the uniform small-\(k\) edge region remains open.

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