Guest User

Untitled

a guest
Jul 20th, 2026
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.12 KB | None | 0 0
  1. # An Improved Upper Bound for Erdős Problem #302
  2.  
  3. 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$.
  4.  
  5. We prove that
  6.  
  7. $\boxed{f(N)\leq \left(\frac{373}{420}+o(1)\right)N}$.
  8.  
  9. Since $\frac{373}{420}\approx 0.888095$, this improves the previously applicable bound $\frac{25}{28}\approx 0.892857$.
  10.  
  11. ## 1. A five-element configuration
  12.  
  13. For each positive integer $t$, define
  14.  
  15. $G_t={2t,3t,4t,6t,12t}$.
  16.  
  17. The elements of $G_t$ contain the three forbidden triples
  18.  
  19. ${2t,3t,6t}$, ${3t,4t,12t}$, and ${4t,6t,12t}$,
  20.  
  21. because
  22.  
  23. $1/(2t)=1/(3t)+1/(6t)$,
  24.  
  25. $1/(3t)=1/(4t)+1/(12t)$,
  26.  
  27. and
  28.  
  29. $1/(4t)=1/(6t)+1/(12t)$.
  30.  
  31. 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.
  32.  
  33. 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$.
  34.  
  35. A single forbidden triple, of course, forces at least one omission.
  36.  
  37. ## 2. A finite tile
  38.  
  39. Define
  40.  
  41. $S={2^i3^j:0\leq i<6,\ 0\leq j<4}\setminus{1}$.
  42.  
  43. Explicitly,
  44.  
  45. $S={2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,72,96,108,144,216,288,432,864}$.
  46.  
  47. For integers $x,y,z$, write $T(x,y,z)$ for the triple ${x,y,z}$ whenever $1/x=1/y+1/z$.
  48.  
  49. We now record lower bounds for the number of elements that must be omitted from each initial segment $S\cap[1,x]$.
  50.  
  51. For $x=6$, the triple $T(2,3,6)$ forces one omission.
  52.  
  53. For $x=12$, the configuration $G_1={2,3,4,6,12}$ forces two omissions.
  54.  
  55. 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.
  56.  
  57. For $x=54$, the preceding three triples together with $T(18,27,54)$ force four omissions.
  58.  
  59. 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.
  60.  
  61. 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.
  62.  
  63. 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.
  64.  
  65. For $x=432$, the preceding configurations together with $T(144,216,432)$ force eight omissions.
  66.  
  67. 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.
  68.  
  69. 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$.
  70.  
  71. Let
  72.  
  73. $R={6,12,48,54,72,96,108,432,864}$.
  74.  
  75. For an admissible set $A$, a scaling factor $a$, and an integer $N$, define
  76.  
  77. $m_A(a,N)=|aS\cap[1,N]\setminus A|$.
  78.  
  79. The preceding certificates show that
  80.  
  81. $m_A(a,N)\geq \sum_{r\in R}\mathbf 1_{{a\leq N/r}}$.
  82.  
  83. Indeed, each time $N/a$ passes one of the thresholds in $R$, the corresponding prefix of $aS$ requires one additional omission.
  84.  
  85. ## 3. Pairwise disjoint scaled tiles
  86.  
  87. Let
  88.  
  89. $\mathcal D={2^{6u}3^{4v}d:u,v\geq0,\ \gcd(d,6)=1}$.
  90.  
  91. For each $a\in\mathcal D$, consider the scaled tile $aS$.
  92.  
  93. We claim that the sets $aS$ are pairwise disjoint.
  94.  
  95. Suppose that
  96.  
  97. $a2^i3^j=a'2^{i'}3^{j'}$,
  98.  
  99. where
  100.  
  101. $a=2^{6u}3^{4v}d$, $a'=2^{6u'}3^{4v'}d'$,
  102.  
  103. with $0\leq i,i'<6$, $0\leq j,j'<4$, and $\gcd(d,6)=\gcd(d',6)=1$.
  104.  
  105. Taking $2$-adic valuations gives
  106.  
  107. $6u+i=6u'+i'$.
  108.  
  109. Reducing modulo $6$ yields $i=i'$, and then $u=u'$.
  110.  
  111. Similarly, taking $3$-adic valuations gives
  112.  
  113. $4v+j=4v'+j'$.
  114.  
  115. Reducing modulo $4$ yields $j=j'$, and then $v=v'$.
  116.  
  117. After cancelling the powers of $2$ and $3$, we obtain $d=d'$. Therefore $a=a'$, proving that the scaled tiles are pairwise disjoint.
  118.  
  119. ## 4. Density of the scaling factors
  120.  
  121. Let
  122.  
  123. $D(X)=|{a\in\mathcal D:a\leq X}|$.
  124.  
  125. Every $a\in\mathcal D$ has the form $a=2^{6u}3^{4v}d$, where $\gcd(d,6)=1$. Hence
  126.  
  127. $D(X)=\sum_{u,v\geq0}#{d\leq X/(2^{6u}3^{4v}):\gcd(d,6)=1}$.
  128.  
  129. Since one third of the positive integers are coprime to $6$,
  130.  
  131. $#{d\leq Y:\gcd(d,6)=1}=Y/3+O(1)$.
  132.  
  133. It follows that
  134.  
  135. $D(X)=\frac{X}{3}\sum_{u\geq0}2^{-6u}\sum_{v\geq0}3^{-4v}+o(X)$.
  136.  
  137. The two geometric series are
  138.  
  139. $\sum_{u\geq0}2^{-6u}=\frac{1}{1-2^{-6}}=\frac{64}{63}$
  140.  
  141. and
  142.  
  143. $\sum_{v\geq0}3^{-4v}=\frac{1}{1-3^{-4}}=\frac{81}{80}$.
  144.  
  145. Therefore
  146.  
  147. $D(X)=\frac{X}{3}\cdot\frac{64}{63}\cdot\frac{81}{80}+o(X)=\frac{12}{35}X+o(X)$.
  148.  
  149. Thus the set $\mathcal D$ has natural density $12/35$.
  150.  
  151. ## 5. Counting omissions
  152.  
  153. Let $A\subseteq{1,\dots,N}$ be admissible, and let
  154.  
  155. $M(N)=N-|A|$
  156.  
  157. be the number of omitted integers.
  158.  
  159. Because the tiles $aS$, with $a\in\mathcal D$, are pairwise disjoint, omissions forced in different tiles may be added. Consequently,
  160.  
  161. $M(N)\geq\sum_{a\in\mathcal D}m_A(a,N)$.
  162.  
  163. Using the prefix estimate from Section 2 gives
  164.  
  165. $M(N)\geq\sum_{a\in\mathcal D}\sum_{r\in R}\mathbf 1_{{a\leq N/r}}$.
  166.  
  167. Interchanging the sums, we obtain
  168.  
  169. $M(N)\geq\sum_{r\in R}D(N/r)$.
  170.  
  171. Since $R$ is finite and $D(X)=\frac{12}{35}X+o(X)$,
  172.  
  173. $M(N)\geq\frac{12}{35}N\sum_{r\in R}\frac1r+o(N)$.
  174.  
  175. Now
  176.  
  177. $\sum_{r\in R}\frac1r=\frac16+\frac1{12}+\frac1{48}+\frac1{54}+\frac1{72}+\frac1{96}+\frac1{108}+\frac1{432}+\frac1{864}$.
  178.  
  179. Using the common denominator $864$, this becomes
  180.  
  181. $\frac{144+72+18+16+12+9+8+2+1}{864}=\frac{282}{864}=\frac{47}{144}$.
  182.  
  183. Therefore
  184.  
  185. $M(N)\geq\frac{12}{35}\cdot\frac{47}{144}N+o(N)=\frac{47}{420}N+o(N)$.
  186.  
  187. Hence
  188.  
  189. $|A|=N-M(N)\leq N-\frac{47}{420}N+o(N)$,
  190.  
  191. and therefore
  192.  
  193. $|A|\leq\left(\frac{373}{420}+o(1)\right)N$.
  194.  
  195. Since this holds for every admissible set $A\subseteq{1,\dots,N}$, we conclude that
  196.  
  197. $\boxed{f(N)\leq\left(\frac{373}{420}+o(1)\right)N}$.
  198.  
  199. Finally,
  200.  
  201. $\frac{373}{420}<\frac{25}{28}$,
  202.  
  203. because $\frac{25}{28}=\frac{375}{420}$. Thus the new estimate improves the previously applicable upper bound by
  204.  
  205. $\frac{25}{28}-\frac{373}{420}=\frac1{210}$.
  206.  
  207. The argument does not determine the true asymptotic value of $f(N)$, but it gives a strictly stronger upper bound.
  208.  
Advertisement
Add Comment
Please, Sign In to add comment