Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # An Improved Upper Bound for Erdős Problem #302
- Let $f(N)$ denote the maximum size of a set $A\subseteq{1,\dots,N}$ containing no three distinct integers $a,b,c\in A$ such that $1/a=1/b+1/c$.
- We prove that
- $\boxed{f(N)\leq \left(\frac{373}{420}+o(1)\right)N}$.
- Since $\frac{373}{420}\approx 0.888095$, this improves the previously applicable bound $\frac{25}{28}\approx 0.892857$.
- ## 1. A five-element configuration
- For each positive integer $t$, define
- $G_t={2t,3t,4t,6t,12t}$.
- The elements of $G_t$ contain the three forbidden triples
- ${2t,3t,6t}$, ${3t,4t,12t}$, and ${4t,6t,12t}$,
- because
- $1/(2t)=1/(3t)+1/(6t)$,
- $1/(3t)=1/(4t)+1/(12t)$,
- and
- $1/(4t)=1/(6t)+1/(12t)$.
- Every four-element subset of $G_t$ contains at least one of these forbidden triples. Indeed, if $2t$ is omitted, then ${3t,4t,12t}$ remains. If $3t$ is omitted, then ${4t,6t,12t}$ remains. If $4t$ is omitted, then ${2t,3t,6t}$ remains. If $6t$ is omitted, then ${3t,4t,12t}$ remains. Finally, if $12t$ is omitted, then ${2t,3t,6t}$ remains.
- Therefore, any admissible set contains at most three elements of $G_t$. Equivalently, it must omit at least two elements from every complete copy of $G_t$.
- A single forbidden triple, of course, forces at least one omission.
- ## 2. A finite tile
- Define
- $S={2^i3^j:0\leq i<6,\ 0\leq j<4}\setminus{1}$.
- Explicitly,
- $S={2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,72,96,108,144,216,288,432,864}$.
- For integers $x,y,z$, write $T(x,y,z)$ for the triple ${x,y,z}$ whenever $1/x=1/y+1/z$.
- We now record lower bounds for the number of elements that must be omitted from each initial segment $S\cap[1,x]$.
- For $x=6$, the triple $T(2,3,6)$ forces one omission.
- For $x=12$, the configuration $G_1={2,3,4,6,12}$ forces two omissions.
- For $x=48$, the three pairwise vertex-disjoint triples $T(2,3,6)$, $T(9,12,36)$, and $T(16,24,48)$ force three omissions.
- For $x=54$, the preceding three triples together with $T(18,27,54)$ force four omissions.
- For $x=72$, the pairwise vertex-disjoint configurations $G_1$, $T(8,9,72)$, $T(16,24,48)$, and $T(18,27,54)$ force $2+1+1+1=5$ omissions.
- For $x=96$, the configurations $G_1$, $G_8$, $T(8,9,72)$, and $T(18,27,54)$ are pairwise vertex-disjoint and force $2+2+1+1=6$ omissions.
- For $x=108$, the configurations $G_1$, $G_8$, $G_9$, and $T(8,9,72)$ are pairwise vertex-disjoint and force $2+2+2+1=7$ omissions.
- For $x=432$, the preceding configurations together with $T(144,216,432)$ force eight omissions.
- For $x=864$, the configurations $G_1$, $G_8$, $G_9$, $G_{72}$, and $T(8,9,72)$ are pairwise vertex-disjoint and force $2+2+2+2+1=9$ omissions.
- All the displayed triples satisfy the required reciprocal identity. For example, $1/8=1/9+1/72$, $1/9=1/12+1/36$, and $1/144=1/216+1/432$.
- Let
- $R={6,12,48,54,72,96,108,432,864}$.
- For an admissible set $A$, a scaling factor $a$, and an integer $N$, define
- $m_A(a,N)=|aS\cap[1,N]\setminus A|$.
- The preceding certificates show that
- $m_A(a,N)\geq \sum_{r\in R}\mathbf 1_{{a\leq N/r}}$.
- Indeed, each time $N/a$ passes one of the thresholds in $R$, the corresponding prefix of $aS$ requires one additional omission.
- ## 3. Pairwise disjoint scaled tiles
- Let
- $\mathcal D={2^{6u}3^{4v}d:u,v\geq0,\ \gcd(d,6)=1}$.
- For each $a\in\mathcal D$, consider the scaled tile $aS$.
- We claim that the sets $aS$ are pairwise disjoint.
- Suppose that
- $a2^i3^j=a'2^{i'}3^{j'}$,
- where
- $a=2^{6u}3^{4v}d$, $a'=2^{6u'}3^{4v'}d'$,
- with $0\leq i,i'<6$, $0\leq j,j'<4$, and $\gcd(d,6)=\gcd(d',6)=1$.
- Taking $2$-adic valuations gives
- $6u+i=6u'+i'$.
- Reducing modulo $6$ yields $i=i'$, and then $u=u'$.
- Similarly, taking $3$-adic valuations gives
- $4v+j=4v'+j'$.
- Reducing modulo $4$ yields $j=j'$, and then $v=v'$.
- After cancelling the powers of $2$ and $3$, we obtain $d=d'$. Therefore $a=a'$, proving that the scaled tiles are pairwise disjoint.
- ## 4. Density of the scaling factors
- Let
- $D(X)=|{a\in\mathcal D:a\leq X}|$.
- Every $a\in\mathcal D$ has the form $a=2^{6u}3^{4v}d$, where $\gcd(d,6)=1$. Hence
- $D(X)=\sum_{u,v\geq0}#{d\leq X/(2^{6u}3^{4v}):\gcd(d,6)=1}$.
- Since one third of the positive integers are coprime to $6$,
- $#{d\leq Y:\gcd(d,6)=1}=Y/3+O(1)$.
- It follows that
- $D(X)=\frac{X}{3}\sum_{u\geq0}2^{-6u}\sum_{v\geq0}3^{-4v}+o(X)$.
- The two geometric series are
- $\sum_{u\geq0}2^{-6u}=\frac{1}{1-2^{-6}}=\frac{64}{63}$
- and
- $\sum_{v\geq0}3^{-4v}=\frac{1}{1-3^{-4}}=\frac{81}{80}$.
- Therefore
- $D(X)=\frac{X}{3}\cdot\frac{64}{63}\cdot\frac{81}{80}+o(X)=\frac{12}{35}X+o(X)$.
- Thus the set $\mathcal D$ has natural density $12/35$.
- ## 5. Counting omissions
- Let $A\subseteq{1,\dots,N}$ be admissible, and let
- $M(N)=N-|A|$
- be the number of omitted integers.
- Because the tiles $aS$, with $a\in\mathcal D$, are pairwise disjoint, omissions forced in different tiles may be added. Consequently,
- $M(N)\geq\sum_{a\in\mathcal D}m_A(a,N)$.
- Using the prefix estimate from Section 2 gives
- $M(N)\geq\sum_{a\in\mathcal D}\sum_{r\in R}\mathbf 1_{{a\leq N/r}}$.
- Interchanging the sums, we obtain
- $M(N)\geq\sum_{r\in R}D(N/r)$.
- Since $R$ is finite and $D(X)=\frac{12}{35}X+o(X)$,
- $M(N)\geq\frac{12}{35}N\sum_{r\in R}\frac1r+o(N)$.
- Now
- $\sum_{r\in R}\frac1r=\frac16+\frac1{12}+\frac1{48}+\frac1{54}+\frac1{72}+\frac1{96}+\frac1{108}+\frac1{432}+\frac1{864}$.
- Using the common denominator $864$, this becomes
- $\frac{144+72+18+16+12+9+8+2+1}{864}=\frac{282}{864}=\frac{47}{144}$.
- Therefore
- $M(N)\geq\frac{12}{35}\cdot\frac{47}{144}N+o(N)=\frac{47}{420}N+o(N)$.
- Hence
- $|A|=N-M(N)\leq N-\frac{47}{420}N+o(N)$,
- and therefore
- $|A|\leq\left(\frac{373}{420}+o(1)\right)N$.
- Since this holds for every admissible set $A\subseteq{1,\dots,N}$, we conclude that
- $\boxed{f(N)\leq\left(\frac{373}{420}+o(1)\right)N}$.
- Finally,
- $\frac{373}{420}<\frac{25}{28}$,
- because $\frac{25}{28}=\frac{375}{420}$. Thus the new estimate improves the previously applicable upper bound by
- $\frac{25}{28}-\frac{373}{420}=\frac1{210}$.
- The argument does not determine the true asymptotic value of $f(N)$, but it gives a strictly stronger upper bound.
Advertisement
Add Comment
Please, Sign In to add comment