\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{lmodern,amsmath,amssymb,amsthm,mathtools} \usepackage[a4paper,hmargin=23mm,vmargin=25mm]{geometry} \usepackage{microtype,xcolor} \usepackage{hyperref} \hypersetup{pdftitle={Small witnesses for eventual Erdos--Straus binomial divisibility},pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{question}[theorem]{Question} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{example}[theorem]{Example} \DeclareMathOperator{\lcm}{lcm} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \title{Small witnesses for eventual Erd\H{o}s--Straus binomial divisibility\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}} \author{Mat\v{e}j Kripner \qquad V\'aclav Rozho\v{n} \qquad Robert \v{S}\'amal\\[0.4em] Martin \v{S}indel\'a\v{r} \qquad Adri\'an Z\'ame\v{c}n\'ik} \date{} % Collection typography; mathematical statements and proofs are unchanged. \definecolor{BolzanoInk}{HTML}{24445C} \hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk, urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}} \urlstyle{same} \setlength{\emergencystretch}{1em} \let\BolzanoBibliography\thebibliography \renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright} \begin{document} \maketitle \begin{abstract} Erd\H{o}s and Straus asked whether, for each fixed $n\ge2$, every sufficiently large integer $m$ admits $1\le k\le m-n$ with $\binom{n+k}{n}\mid\binom{m+k}{k}$. We prove that it does; previously this was known only for a set of $m$ of density one. The witness can be taken with $k=O_{n,\varepsilon}(m^\varepsilon)$ for every $\varepsilon>0$: a factorial identity reduces the problem to finding a small value of a fixed polynomial coprime to $\binom mn$, which an elementary sieve provides. Conversely, the least witness is at least logarithmic in $m$ along an infinite sequence. \end{abstract} \section{Introduction} \subsection{Background and the source problem} For positive integers $n,k$, write $A(n,k)=(n+1)\cdots(n+k)$. Comparing two such products is easy in size but difficult in divisibility: increasing every factor does not ensure that the larger product contains the prime powers of the smaller one. Erd\H{o}s and Straus asked how much freedom in the common length $k$ suffices to obtain $A(n,k)\mid A(m,k)$ \cite{ES}. Since \[ \frac{A(m,k)}{A(n,k)} =\frac{\binom{m+k}{k}}{\binom{n+k}{n}}, \] their question has a binomial formulation. The restriction $k\le m-n$ keeps the two intervals disjoint. Without it, the factorial identity $A(m,k)/A(n,k)=A(n+k,m-n)/A(n,m-n)$ provides easy, potentially very large witnesses. The following is the fixed-$n$ question in \cite[\S1, p.~66, (1.4)]{ES}; it is also restated in \cite[Appendix C.5.1]{FAR}. \begin{question}[{Erd\H{o}s--Straus, \cite[\S1, (1.4)]{ES}}] For a fixed integer $n\ge2$, does every sufficiently large integer $m$ admit an integer $k$ satisfying \begin{equation}\label{eq:target} 1\le k\le m-n, \qquad \binom{n+k}{n}\mid\binom{m+k}{k}? \end{equation} If not, what is the density of the integers admitting such a witness? \end{question} \begin{definition} For $n\ge2$, let $G_n$ be the set of integers $m>n$ for which \eqref{eq:target} has a solution. The natural density of a set $S\subseteq\N$, when it exists, is $\lim_{X\to\infty}|S\cap[1,X]|/X$. Its natural lower density is $\liminf_{X\to\infty}|S\cap[1,X]|/X$. \end{definition} There are two substantially different parameter regimes. When $m/n$ is bounded and $k$ is at least a fixed positive multiple of $n$, Erd\H{o}s and Straus prove that no solutions exist once $n$ is large enough \cite[Theorem 2.1]{ES}. The question above instead keeps $n$ fixed and lets $m$ tend to infinity. The best previous result in this regime is the density-one theorem of Zheng, Zhang, Avigad, Tetali and Welleck \cite[Theorem C.5.1]{FAR}, whose authors state that ``whether all large $m$ lie in $G_n$ remains open'' \cite[Remark C.5.2]{FAR} and note that their proof gives no bound for the least admissible $k$. \subsection{Main results} We answer the first part of the question affirmatively: for every fixed $n\ge2$, the set $G_n$ contains every sufficiently large integer, so the density question becomes moot. More precisely: \begin{enumerate} \item Proposition~\ref{prop:witness} gives, for every $m>n$, a positive $k$ with $\binom{n+k}{n}\mid\binom{m+k}{k}$ and $k\le n!((n+1)^{2\omega(\binom mn)}+1)$, where $\omega$ counts distinct prime factors. \item Theorem~\ref{thm:eventual} gives an explicit threshold above which this witness lies in $[1,m-n]$, and Corollary~\ref{cor:subpoly} shows that it is $O_{n,\varepsilon}(m^{\varepsilon})$ for every $\varepsilon>0$. \item Theorem~\ref{thm:lower} shows that the least witness is at least $(\log m)/\log 16-n+2$ along an infinite sequence of $m$, while it equals one on another infinite sequence. Thus no fixed finite list of lengths serves all large $m$. \end{enumerate} The asymptotic assertions keep $n$ fixed; their constants need not be uniform as $n$ grows. Since the constructed $k$ is a positive multiple of $n!$ and is $o(m)$, it eventually satisfies even $1(n+1)^{2r}$ therefore works regardless of the sizes of the primes. For example, at $n=2$ the progression is $k=2t$ and the polynomial is $(1+2t)(1+t)$. An exponential bound in $r$ suffices because $C^{\omega(N)}=O_{C,\delta} (N^\delta)$ for every fixed $C>1$ and $\delta>0$, whereas $N\le m^n$. The resulting witness is smaller than every fixed positive power of $m$, and consequently fits in the permitted interval. The lower bound reverses the arithmetic strategy. When $m$ is a multiple of a sufficiently large prime power $p^a$ and $kd+1$, it is at least $1-d/p>1/(d+1)$. For $A\subseteq\mathcal P$, put $q_A=\prod_{p\in A}p$ and $\rho_A=\prod_{p\in A}\rho(p)$, using empty products equal to one. The Chinese remainder theorem implies that $q_A\mid F(t)$ holds in exactly $\rho_A$ residue classes modulo $q_A$. A residue class contains $T/q_A$ integers in $[1,T]$ with error of absolute value at most one. Thus, for positive integer $T$, \[ \#\{1\le t\le T:q_A\mid F(t)\} =\frac{\rho_A T}{q_A}+E_A, \qquad |E_A|\le\rho_A. \] For $A=\varnothing$ the count is exactly $T$, so $E_A=0$ is allowed. Inclusion--exclusion now yields \begin{align} S(T)&:=\#\{1\le t\le T:\gcd(F(t),N)=1\}\notag\\ &=T\prod_{p\in\mathcal P}\left(1-\frac{\rho(p)}p\right)+E, & |E|&\le\prod_{p\in\mathcal P}(1+\rho(p))\le(d+1)^r. \label{eq:sieve-count} \end{align} Together with \eqref{eq:density}, this gives $S(T)\ge T/(d+1)^r-(d+1)^r$. At $T=(d+1)^{2r}+1$ the right side is $(d+1)^{-r}>0$. The integer count $S(T)$ is therefore positive. Empty products give the same conclusion when $N=1$. \end{proof} \begin{lemma}\label{lem:omega} For $C>1$, $\delta>0$ and positive integer $N$, \begin{equation}\label{eq:omega} C^{\omega(N)}\le C^{\pi(C^{1/\delta})}N^\delta. \end{equation} \end{lemma} \begin{proof} Set $R=C^{1/\delta}$. In the product $C^{\omega(N)}=\prod_{p\mid N}C$, primes at most $R$ contribute at most $C^{\pi(R)}$. For each remaining prime, $Cn\ge2$, there exists a positive multiple $k$ of $n!$ such that \begin{equation}\label{eq:witness} \binom{n+k}{n}\mid\binom{m+k}{k}, \qquad k\le n!\left((n+1)^{2\omega(\binom mn)}+1\right). \end{equation} This assertion alone imposes no upper bound $m-n$ on $k$. \end{proposition} \begin{proof} Define \begin{equation}\label{eq:Fn} F_n(t)=\prod_{j=1}^n\left(1+\frac{n!}{j}t\right). \end{equation} Each $j$ divides $n!$, so $F_n\in\Z[t]$, its degree is $n$, and $F_n(0)=1$. For nonnegative integer $t$, multiplication of the factors gives \[ F_n(t)=\frac{(n!t+1)\cdots(n!t+n)}{n!} =\binom{n+n!t}{n}. \] Lemma~\ref{lem:sieve} produces a positive $t$ at most $(n+1)^{2\omega(\binom mn)}+1$ for which $F_n(t)$ is coprime to $\binom mn$. Put $k=n!t$ and apply Lemma~\ref{lem:coprime}. \end{proof} \begin{theorem}\label{thm:eventual} For $n\ge2$, define \begin{equation}\label{eq:threshold} B_n=(n+1)^{4n},\qquad D_n=(n+1)^{2\pi(B_n)},\qquad M_n=\max\{4(n!D_n)^2,\,2(n+n!)\}. \end{equation} Every integer $m\ge M_n$ belongs to $G_n$. \end{theorem} \begin{proof} The threshold exceeds $n$. Set $N=\binom mn$. Apply Lemma~\ref{lem:omega} with $C=(n+1)^2$ and $\delta=1/(2n)$. Since $C^{1/\delta}=B_n$, it gives $(n+1)^{2\omega(N)}\le D_nN^{1/(2n)}$. Also $N\le m^n$. The witness furnished by Proposition~\ref{prop:witness} therefore satisfies \begin{equation}\label{eq:sqrt} k\le n!D_n\sqrt m+n!. \end{equation} The first condition in \eqref{eq:threshold} implies $n!D_n\sqrt m\le m/2$, and the second gives $n!\le m/2-n$. Substitution in \eqref{eq:sqrt} proves $k\le m-n$. Positivity and divisibility follow from Proposition~\ref{prop:witness}. \end{proof} \begin{remark} The word ``eventual'' is necessary: $m=n+1$ never belongs to $G_n$. The only permitted value is $k=1$, which would require $n+1$ to divide $n+2$. This fails for $n\ge2$. The threshold in Theorem~\ref{thm:eventual} gives a finite interval containing all exceptions; it does not identify those exceptions. \end{remark} \begin{corollary}\label{cor:subpoly} For fixed $n\ge2$ and $\varepsilon>0$, a constant $K_{n,\varepsilon}$ exists such that each $m>n$ has a positive divisibility witness $k\le K_{n,\varepsilon}m^\varepsilon$. If $m\ge M_n$, the witness can simultaneously be chosen in $[1,m-n]$. \end{corollary} \begin{proof} In Lemma~\ref{lem:omega}, take $C=(n+1)^2$ and $\delta=\varepsilon/n$. Writing $A_{n,\varepsilon}=(n+1)^{2\pi((n+1)^{2n/\varepsilon})}$ gives \[ (n+1)^{2\omega(\binom mn)} \le A_{n,\varepsilon}\binom mn^{\varepsilon/n} \le A_{n,\varepsilon}m^\varepsilon. \] Every witness selected by the construction in Proposition~\ref{prop:witness} obeys this bound and the bound used in Theorem~\ref{thm:eventual}. Thus one can take $K_{n,\varepsilon}=n!(A_{n,\varepsilon}+1)$, with both conclusions holding for the same selected witness. \end{proof} \begin{example} For $n=2$, the polynomial is $F_2(t)=(1+2t)(1+t)$. At $m=10$, $\binom{10}{2}=45$. The choices $t=1,2$ give values $6,15$, which are not coprime to $45$; $t=3$ gives $28$, which is. Thus $k=6\le10-2$ is an admissible witness, and indeed $\binom82=28$ divides $\binom{16}6=8008$. The sieve guarantees the existence of such a choice; its general upper bound is not intended to be close to the first successful $t$. \end{example} \section{Lower bounds for the least witness} \begin{definition} For integers $m>n\ge2$, define \[ \kappa_n(m)=\min\left\{k\in\Z_{\ge1}:\binom{n+k}{n}\mid\binom{m+k}{k}\right\}. \] Proposition~\ref{prop:witness} ensures that this minimum exists. For $m\ge M_n$, it is also the least witness in the original permitted interval. Write $L_s=\lcm(1,\ldots,s)$, and use natural logarithms. For a prime $p$, $v_p(r)$ denotes the exponent of $p$ in a positive integer $r$. \end{definition} \begin{lemma}\label{lem:congruence} If $p$ is prime, $p^a\mid m$ with $a\ge1$, and $0\le ku$ and $p^{a-1}\le s/p\le s/2\le u$. Hence $p$ occurs in $L_s/L_u$ to exponent exactly one. Counting multiples of $p^j$ in each factorial gives $v_p(r!)=\sum_{j\ge1}\lfloor r/p^j\rfloor$, and hence \[ v_p\left(\binom sv\right) =\sum_{j\ge1}\left( \left\lfloor\frac s{p^j}\right\rfloor- \left\lfloor\frac u{p^j}\right\rfloor- \left\lfloor\frac v{p^j}\right\rfloor\right). \] Each term is nonnegative since $s=u+v$. The term at $j=a$ is one, because $u,vn$ and $\kappa_n(m)>K$. In particular, the set of such $m>n$ with $\kappa_n(m)>K$ has natural lower density at least $L_{K+n}^{-2}$. \end{proposition} \begin{proof} Put $x=K+n$. Since $x\mid L_x$, we have $m\ge x^2>n$. For a prime $p\le x$, let $e\ge1$ satisfy $p^e\le xx$. Lemma~\ref{lem:congruence} therefore gives $\binom{m+k}{k}\equiv1\pmod p$ for every $1\le k\le K$. On the other hand, $\binom{n+k}{n}>1$ and every one of its prime factors is at most $n+k\le x$, as follows from $\binom{n+k}{n}n!k!=(n+k)!$. The two binomial coefficients are coprime; the first cannot divide the second. This excludes every $k\le K$. Finally, the number of positive multiples of $L_x^2$ up to $X$ is $\lfloor X/L_x^2\rfloor$. Dividing by $X$ and taking the lower limit proves the density claim. \end{proof} \begin{remark} For a fixed $K$, every sufficiently large member of the progression in Proposition~\ref{prop:progression} nevertheless belongs to $G_n$ by Theorem~\ref{thm:eventual}. Its admissible witnesses then lie above $K$. Thus eventual existence requires the witness length to vary with $m$. \end{remark} \begin{theorem}\label{thm:lower} For fixed $n\ge2$ and integers $x\ge n+1$, let $m_x=L_x^2$. Then $m_x\to\infty$ and \begin{equation}\label{eq:lower} \kappa_n(m_x)\ge x-n+1 \ge\frac{\log m_x}{\log16}-n+2. \end{equation} Consequently \[ \limsup_{m\to\infty}\frac{\kappa_n(m)}{\log m}\ge\frac1{\log16}, \qquad \liminf_{m\to\infty}\frac{\kappa_n(m)}{\log m}=0. \] Both limits range over integers $m>n$. Thus a uniform $o(\log m)$ upper bound for positive witnesses is impossible. \end{theorem} \begin{proof} Since $L_x\ge x$, the integers $m_x$ tend to infinity. Proposition~\ref{prop:progression} with $K=x-n$ gives $\kappa_n(m_x)>x-n$. Integrality gives the first inequality in \eqref{eq:lower}. Lemma~\ref{lem:lcm} implies $m_x\le16^{x-1}$, and hence $x\ge1+\log m_x/\log16$. This proves the second inequality. Division by $\log m_x$ gives the stated lower bound for the limit superior. The sequence $m_x$ need not be strictly increasing; its divergence to infinity is all that this limit argument uses. For the limit inferior, choose $m=(n+1)q-1$ with integer $q\ge2$. Then $m>n$, $1\le m-n$, and \[ \binom{n+1}{n}=n+1\mid m+1=\binom{m+1}{1}. \] Thus $\kappa_n(m)=1$ on an infinite progression. The corresponding ratios tend to zero, and all ratios are nonnegative, proving the limit-inferior assertion. A uniform $o(\log m)$ bound would contradict the positive limit superior. Finally, $m_x\ge M_n$ for sufficiently large $x$, so these lower bounds then concern witnesses that also exist in $[1,m_x-n]$. \end{proof} \section{Concluding remarks} The bounds leave a considerable gap between logarithmic growth along a sequence and a subpolynomial uniform upper bound. Determining the maximal order of the least witness remains a quantitative problem. The explicit threshold in \eqref{eq:threshold} is a consequence of a coarse prime-factor estimate and is not asserted to be close to optimal. Since the constructed witness is a positive multiple of $n!$ and is $o(m)$, it also satisfies $1