Erdős Problem #376

Problem 376. Infinitely many $n$ with $\gcd\!\left(\binom{2n}{n},105\right)=1$? --- Round 2

1) ROUND-2 OBJECTIVE

Path (C): isolate a fatal obstruction in the strongest currently available fractal-intersection strategy, and correct an overoptimistic reading of the literature.

Round 1 already gave the exact Kummer digit reformulation and the unconditional two-prime theorem. What remained unclear was whether recent fractal technology gives an unconditional power-saving upper bound for the specific triple $(3,5,7)$. In this round I show that the answer is no: the existing method needs an extra linear-independence input which is not currently known for $(3,5,7)$.

This is strict progress because it identifies the exact missing hypothesis needed to push current methods onto Problem 376.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

• By Kummer's theorem, \[ \gcd\!\left(\binom{2n}{n},105\right)=1 \] if and only if all base-$3$ digits of $n$ lie in $\{0,1\}$, all base-$5$ digits lie in $\{0,1,2\}$, and all base-$7$ digits lie in $\{0,1,2,3\}$.
• Erdős--Graham--Ruzsa--Straus proved infinitude for any two odd primes.
• Round 1 recorded that the three-prime problem for $105$ remains open.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a careful reading of Burrell--Yu's three-base intersection theorem.

Their method does give a power-saving upper bound for the counting function \[ G_{3,5,7}(N):=\#\left\{n\le N:\gcd\!\left(\binom{2n}{n},105\right)=1\right\}, \] but only under the extra hypothesis that \[ 1,\ \frac{\log 3}{\log 5},\ \frac{\log 3}{\log 7} \] are linearly independent over the rationals (equivalently, that $(3,5,7)$ is strongly multiplicatively independent in their terminology).

Unconditionally, they prove only that at least one of the triples \[ (3,5,7),\qquad (3,5,11),\qquad (3,5,13) \] has the required independence property. That existential statement is not enough to say anything unconditional about $105$ itself.

4) ATTACK PLAN (ROUND-2)

The exact gap after Round 1 is this:

I will answer this in two steps.

1. State precisely the extra hypothesis Burrell--Yu need in order to get a power-saving upper bound for $(3,5,7)$.
2. Show that their unconditional theorem is only existential in the third prime $q\in\{7,11,13\}$, so it cannot be specialized to $q=7$.

This isolates the exact obstruction in the present proof strategy.

5) WORK (ROUND-2)

Proposition 5.1 (conditional power-saving for Problem 376)

Assume that \[ 1,\ \frac{\log 3}{\log 5},\ \frac{\log 3}{\log 7} \] are linearly independent over the rationals. Then \[ G_{3,5,7}(N)\ll N^{\theta_{3,5,7}+o(1)}, \qquad \theta_{3,5,7}:=\frac{\log 2}{\log 3}+\frac{\log 3}{\log 5}+\frac{\log 4}{\log 7}-2. \] In particular, \[ G_{3,5,7}(N)\ll N^{0.026} \] for all sufficiently large $N$.

Justification.

Burrell--Yu's three-base intersection theorem applies to digit-restricted sets in strongly multiplicatively independent bases. For Problem 376 the allowed digit counts are \[ 2 \text{ in base }3,\qquad 3 \text{ in base }5,\qquad 4 \text{ in base }7. \] Hence the relevant dimension sum is \[ \frac{\log 2}{\log 3}+\frac{\log 3}{\log 5}+\frac{\log 4}{\log 7}, \] and their theorem yields an upper bound of exponent equal to this quantity minus $2$. Numerically, \[ \theta_{3,5,7}\approx 0.0259<0.026. \] So under the displayed linear-independence hypothesis one gets \[ G_{3,5,7}(N)\ll N^{0.026}. \] Under Schanuel's conjecture this linear independence is available, so the same conditional upper bound follows.

Proposition 5.2 (the exact unconditional obstruction)

Burrell--Yu's unconditional argument does not imply any power-saving upper bound for the specific set $G_{3,5,7}(N)$.

Proof.

Their notion of strong multiplicative independence for three bases $(p_1,p_2,p_3)$ is exactly the linear independence over the rationals of \[ 1,\ \frac{\log p_1}{\log p_2},\ \frac{\log p_1}{\log p_3}. \] For the triple $(3,5,7)$ this becomes \[ 1,\ \frac{\log 3}{\log 5},\ \frac{\log 3}{\log 7}. \] Burrell--Yu do not prove this unconditionally.

What they do prove unconditionally is weaker: by a six-exponentials argument they show that at least one of \[ (3,5,7),\qquad (3,5,11),\qquad (3,5,13) \] is strongly multiplicatively independent. Consequently, one gets a power-saving upper bound for at least one of the three counting functions \[ G_{3,5,7}(N),\qquad G_{3,5,11}(N),\qquad G_{3,5,13}(N), \] but not necessarily for the first one.

In the worst case the independent triple is only $(3,5,13)$, whose exponent is \[ \theta_{3,5,13} = \frac{\log 2}{\log 3}+\frac{\log 3}{\log 5}+\frac{\log 7}{\log 13}-2 \approx 0.0722<0.073. \] Thus the unconditional output of that paper is merely: \[ \text{for at least one } q\in\{7,11,13\},\quad G_{3,5,q}(N)\ll N^{0.073}, \] and this gives no unconditional upper bound for Problem 376 itself.

Corollary 5.3 (a sharply formulated obstruction)

The present three-fractal strategy would settle the upper-bound side of Problem 376 if one could prove \[ 1,\ \frac{\log 3}{\log 5},\ \frac{\log 3}{\log 7} \] are linearly independent over the rationals. At present this is the exact missing hypothesis blocking that route.

6) ADVERSARIAL VERIFICATION

Potential failure modes:

• Did I accidentally turn an existential theorem into a theorem for $q=7$? No. This is precisely what I ruled out. The unconditional theorem says "for at least one $q\in\{7,11,13\}$", not "for each such $q$".

• Is the exponent $0.026$ unconditional for $105$? No. In the argument above it is explicitly conditional on the displayed linear independence (for example via Schanuel).

• Does this settle the original infinitude problem? No. Even a power-saving upper bound still allows infinitely many solutions. This round isolates an obstruction in one proof strategy; it does not prove finiteness or infinitude.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict Round-2 advance is a precise obstruction theorem: current three-base fractal methods do not give an unconditional upper bound for the specific problem with $105$. They would yield \[ G_{3,5,7}(N)\ll N^{0.026} \] under the extra hypothesis that \[ 1,\ \frac{\log 3}{\log 5},\ \frac{\log 3}{\log 7} \] are linearly independent over the rationals, but unconditionally they prove only that one of the triples $(3,5,7)$, $(3,5,11)$, $(3,5,13)$ enjoys a power-saving upper bound. So the exact missing ingredient for this route is now sharply identified.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 48%

9) REFERENCES

[EGRS75] P. Erdős, R. L. Graham, I. Z. Ruzsa, and E. G. Straus, On the prime factors of $\binom{2n}{n}$, Math. Comp. 29 $1975$, 83--92.

[BY] S. A. Burrell and H. Yu, Digit expansions of numbers, arXiv:1905.00832.

[BC25] T. F. Bloom and E. Croot, Integers with small digits in multiple bases, arXiv:2509.02835.

OBJECTIVE AND SOURCE REVIEW

Erdős #376; independent attempt, 2026-09-23. Are there infinitely many positive $n$ with $\gcd(\binom{2n}{n},105)=1$? I read all of 376.tex. It carefully labels the proposed very small exponent conditional, but its broader assertion that no unconditional power-saving upper bound is available is false literally: one base already provides one. I make that distinction precise and independently enumerate a bounded range.

WORK: AN UNCONDITIONAL BASELINE AND EXACT CHECK

By the digit characterization, every admissible $n<3^k$ has only digits zero or one in its $k$ base-three positions. There are exactly $2^k$ such nonnegative integers. Consequently \[ G_{3,5,7}(N)\le2(N+1)^{\log_3 2}. \] To justify the digit condition directly, Legendre's factorial valuation gives $v_p(\binom{2n}{n})=\sum_{j\ge1}(\lfloor2n/p^j\rfloor-2\lfloor n/p^j\rfloor)$, the number of carries on doubling $n$ in base $p$. There are no carries exactly when every digit is at most $(p-1)/2$. The saved program verification/batch_3_digits_records.py generates all $2^{20}$ zero-one base-three strings and tests their base-five and base-seven digits. It finds exactly 14 positive solutions below $3^{20}=3486784401$: \[ 1,10,756,757,3160,3186,3187,3250,7560,7561,7651, 20007,59548377,59548401. \] The list and bounds are saved in its JSON output. This is an exact bounded reproduction check, not a claimed record search.

ADVERSARIAL VERIFICATION AND REMAINING GAP

Leading zero digits are permitted, ensuring every integer below the cutoff is considered. Zero is explicitly excluded from the displayed list. The unconditional exponent $\log_3 2$ is much larger than the source's conditional $0.026$; it does not validate that stronger assertion. Neither any power-saving upper bound nor a finite list proves finiteness or infinitude. Constructing arbitrarily large simultaneous digit-restricted integers remains the exact gap.

SOURCES CHECKED

Complete local source gpt_pro_5.4/376.tex; official primary statement and digit equivalence checked at https://www.erdosproblems.com/latex/376, 2026-09-23.

FINAL

UNRESOLVED. A literal overstatement about unconditional bounds is corrected and a bounded exhaustive check reproduced.

COMPLETION ESTIMATE

Conservative subjective progress toward infinitude. COMPLETION: 8%

Problem 376. Infinitely many $n$ with $\binom{2n}{n}$ coprime to $105$?

FORMAL RESTATEMENT

Determine whether the set \[ \mathcal{S}:=\{n\in\mathbb{N}: \gcd\!\left(\binom{2n}{n},105\right)=1\} \] is infinite.

QUICK LITERATURE / CONTEXT CHECK

This problem is stated as open in Erdős--Graham $1980$ and remains open in the Erdős problems database.

A key equivalence comes from Kummer's theorem: for a prime $p$, $p\nmid \binom{2n}{n}$ iff there are no carries when adding $n+n$ in base $p$, which is equivalent to every base-$p$ digit of $n$ being $<p/2$.

Erdős--Graham--Ruzsa--Straus $1975$ prove that for any two odd primes $p,q$ there are infinitely many $n$ with $\binom{2n}{n}$ coprime to $pq$.

For the specific triple $(3,5,7)$, many examples are known computationally (OEIS A030979 begins $0,1,10,756,757,3160,3186,3187,3250,\dots$), but infinitude is unknown. Bloom--Croot $2025$ give a "weak" result for $\ge 3$ primes when the primes are sufficiently large: they produce infinitely many $n$ for which almost all base-$p$ digits are $<p/2$, implying $\binom{2n}{n}$ is coprime to the product of those primes up to a factor $\le n^\varepsilon$.

Conditional and quantitative information can be found in work of Han Yu $2022$: under Schanuel's conjecture and an additional conjecture on thickness, the set $\mathcal{S}$ is infinite; under Schanuel's conjecture one has a power-saving upper bound $\#(\mathcal{S}\cap[1,N])\ll N^{0.026\dots}$.

ATTACK PLAN

1. Use Kummer/Lucas to rewrite the gcd condition as a digit restriction in bases $3,5,7$.
2. Interpret each digit-restricted set as a Cantor-like set; the problem becomes whether three multiplicatively independent Cantor sets have infinite intersection.
3. Current approaches in the literature include: (i) "carry-poor" constructions (EGRS for $r=2$; Bloom--Croot for $r\ge 3$ but with exceptions), and (ii) fractal-geometry methods (Newhouse gap lemma, thickness) giving conditional results and upper bounds.
4. A full resolution for $(3,5,7)$ would likely require a new mechanism forcing simultaneous small-digit expansions in three small bases (or proving this cannot happen beyond finitely many $n$).

WORK

1. Digit formulation via Kummer

Let $p$ be a prime and write the base-$p$ expansion \[ n=\sum_{j\ge 0} a_j p^j,\qquad 0\le a_j\le p-1. \] Kummer's theorem states that the $p$-adic valuation $\nu_p\!\left(\binom{2n}{n}\right)$ equals the number of carries when adding $n+n$ in base $p$. In particular, \[ p\nmid \binom{2n}{n} \iff \text{no carries occur in }n+n\text{ (base }p) \iff \forall j,\ 2a_j\le p-1 \iff \forall j,\ a_j\le \frac{p-1}{2}. \] Thus \[ \gcd\!\left(\binom{2n}{n},105\right)=1 \iff \begin{cases} \text{all base-}3\text{ digits of }n\text{ lie in }\{0,1\},\\ \text{all base-}5\text{ digits of }n\text{ lie in }\{0,1,2\},\\ \text{all base-}7\text{ digits of }n\text{ lie in }\{0,1,2,3\}. \end{cases} \] The example $756=(1001000)_3=(11011)_5=(2130)_7$ is one explicit solution.

2. What is known unconditionally

• (Two primes.) EGRS $1975$ prove that for any two odd primes $p,q$ there are infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $pq$. This corresponds to the existence of infinitely many integers whose base-$p$ digits are $<p/2$ and base-$q$ digits are $<q/2$.
• (Three primes, small.) For $(3,5,7)$ the problem is open. Direct computation gives at least the following 12 solutions up to $20000$: \[ 0,1,10,756,757,3160,3186,3187,3250,7560,7561,7651. \] These agree with the initial segment of OEIS A030979.

3. Partial progress toward $r\ge 3$

Bloom--Croot $2025$ show that for $r\ge 1$, if $g_1,\dots,g_r$ are distinct coprime integers that are sufficiently large (depending only on $r$), then for every $\varepsilon>0$ there are infinitely many integers $n$ such that, simultaneously for all $i$, all but at most $\varepsilon\log n$ of the base-$g_i$ digits of $n$ are $\le g_i/2$. Their Corollary 1 yields (for $r\ge 3$ and sufficiently large primes $p_i$) a factorisation \[ \binom{2n}{n}=n_1 n_2, \qquad (n_1,p_1\cdots p_r)=1,\quad n_2\le n^{\varepsilon}, \] which is a "weak" version of the desired coprimality.

Han Yu $2022$ gives conditional results in the exact direction of Problem 376: under Schanuel's conjecture and an additional conjecture on thickness of the digit sets, the intersection for bases $(3,5,7)$ is infinite; under Schanuel one also gets a strong power-saving upper bound on the counting function.

VERIFICATION

The equivalence between $p\nmid\binom{2n}{n}$ and the digit condition is standard via Kummer's carry interpretation; the digit condition for $105$ is just the conjunction for $p\in\{3,5,7\}$. The numerical list up to $20000$ was verified by a brute-force digit check.

FINAL

LABEL: UNRESOLVED.
SUB-LABEL: N/A.
The problem for $105=3\cdot 5\cdot 7$ is open. We recorded the exact digit reformulation, the unconditional $r=2$ theorem of Erdős--Graham--Ruzsa--Straus, and partial $r\ge 3$ results (Bloom--Croot; Yu), plus computational evidence.

COMPLETION ESTIMATE

A full solution would require either (i) a new construction producing infinitely many integers with simultaneously small digits in bases $3,5,7$ (no carries in all three bases), or (ii) a proof that the intersection is finite. Existing methods handle $r=2$ strongly, and $r\ge 3$ only in a weakened "almost all digits" sense or under strong transcendence/fractal hypotheses.