Número entero máximo que no está en $\{ ax+by : \gcd(a,b) = 1 \land a,b \ge 0 \}$

Question

Ryan preguntó sobre una variación del problema de la moneda que era si para cualquier número natural coprimo $x,y$ todo número natural suficientemente grande es $ax+by$ para algunos números naturales coprimos $a,b$ . Batominovski demostró que esta conjetura es efectivamente cierta y que el máximo número natural irrepresentable es $O((xy)^{1+})$ para cualquier $ > 0$ . Pero un límite inferior obvio es $(xy)$ dejando un hueco. Entonces conjeturé que de hecho es asintóticamente $( xy \ln(xy) )$ como $x,y \to \infty$ y su trama para $xy \in [1..2500]$ parece apoyar esta suposición salvaje.

¿Puede alguien probar o refutar mi conjetura?

Answer 1

Con un argumento heurístico, puedo demostrar que, si $z$ es un número entero con $z \gtrsim \zeta(2)\,xy\,\ln(xy)$ entonces $z$ puede escribirse como $ax+by$ con $a,b\in\mathbb{Z}_{\geq 0}$ tal que $\gcd(a,b)=1$ . Esto significaría que $$xy-1\leq m(x,y)\lesssim \zeta(2)\,xy\,\ln(xy)\,,$$ si $m(x,y)$ es el mayor número entero que no está en $\big\{ax+by\,\big|\,a,b\in\mathbb{Z}_{\geq 0}\,\text{ and }\gcd(a,b)=1\big\}$ . (Aquí, $\zeta$ es la función zeta de Riemann).

Obsérvese que las soluciones enteras $(a,b)$ a la ecuación $ax+by=z$ son de la forma $$(a,b)=\left(a_0+ky,b_0-kx\right)$$ para algunos $a_0,b_0\in\mathbb{Z}$ , donde $k\in\mathbb{Z}$ es arbitraria. De ellos, hay aproximadamente $\frac{z}{xy}$ soluciones $(a,b)$ con $a,b\geq 0$ .

Considere un primo $p\nmid \gcd(xy,z)$ . La probabilidad de que $p$ divide $a_0+ky$ es $\frac{1}{p}$ y la probabilidad de que $p$ divide $b_0-kx$ es $\frac{1}{p}$ . Por lo tanto, aproximadamente, la probabilidad de que $p$ divide ambos $a_0+ky$ y $b_0-kx$ es $\frac{1}{p^2}$ . (Tenga en cuenta que el caso de que $a_0+ky$ es divisible por $p$ y el evento que $b_0-kx$ es divisible por $p$ no son del todo independientes; por lo tanto, este argumento no es válido, pero como he dicho, se trata de un argumento heurístico).

Considere un primo $p\mid \gcd(xy,z)$ . Entonces, o bien $p\mid x$ o $p\mid y$ pero no ambos. Sin pérdida de generalidad, supongamos que $p\mid x$ . Entonces, como $p\mid z$ tenemos $p\mid b_0$ y $p$ siempre divide $b_0-kx$ . La probabilidad de que $p$ también divide $a_0+ky$ es $\frac{1}{p}$ .

En consecuencia, entre las soluciones enteras no negativas $(a,b)$ a $ax+by=z$ , aproximadamente $$\frac{z}{xy}\,\prod_{\substack{{p\text{ prime}}\\{p\nmid \gcd(xy,z)}}}\,\left(1-\frac{1}{p^2}\right)\,\prod_{\substack{{p\text{ prime}}\\{p\mid \gcd(xy,z)}}}\,\left(1-\frac{1}{p}\right)=\frac{z}{xy}\,\frac{\displaystyle\prod_{p\text{ prime}}\,\left(1-\frac{1}{p^2}\right)}{\displaystyle \prod_{\substack{{p\text{ prime}}\\{p\mid \gcd(xy,z)}}}\,\left(1+\frac{1}{p}\right)}$$ tienen la propiedad de que $\gcd(a,b)=1$ . Por lo tanto, necesitamos $$\frac{z}{xy}\,\frac{\displaystyle\prod_{p\text{ prime}}\,\left(1-\frac{1}{p^2}\right)}{\displaystyle \prod_{\substack{{p\text{ prime}}\\{p\mid \gcd(xy,z)}}}\,\left(1+\frac{1}{p}\right)}\gtrsim 1\,.$$ Sin embargo, tenga en cuenta que $$\prod_{\substack{{p\text{ prime}}\\{p\mid \gcd(xy,z)}}}\,\left(1+\frac{1}{p}\right)\leq\sum_{j=1}^{\gcd(xy,z)}\,\frac{1}{j}\leq\sum_{j=1}^{xy}\,\frac{1}{j}\approx \ln(xy)$$ y $$\prod_{p\text{ prime}}\,\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}\,.$$ Desde $z\gtrsim\zeta(2)\,xy\,\ln(xy)$ obtenemos $$\frac{z}{xy}\,\frac{\displaystyle\prod_{p\text{ prime}}\,\left(1-\frac{1}{p^2}\right)}{\displaystyle \prod_{\substack{{p\text{ prime}}\\{p\mid \gcd(xy,z)}}}\,\left(1+\frac{1}{p}\right)}\gtrsim \frac{z}{\zeta(2)\,xy\,\ln(xy)}\gtrsim 1\,.$$

A continuación se muestra un gráfico para ilustrar que este límite superior de $m(x,y)$ funciona bien para la mayoría de los valores de $x$ y $y$ . En esta parcela, $x,y\in\{1,2,\ldots,100\}$ . La curva magenta viene dada por $m(x,y)=\zeta(2)\,xy\,\ln(xy)$ la curva roja viene dada por $m(x,y)=xy\,\ln(xy)$ y la línea cian es el límite inferior $m(x,y)=xy-1$ . El gráfico azul disperso es el actual $xy$ -versus- $m(x,y)$ parcela. Por lo tanto, ahora creo que $\displaystyle\limsup_{xy\to\infty}\,\frac{m(x,y)}{xy\,\ln(xy)}$ está muy cerca de $\zeta(2)$ .

Para $x,y\in\{1,2,\ldots,100\}$ con $x\leq y$ Sólo hay $18$ se empareja con $m(x,y)>\zeta(2)\,xy\,\ln(xy)$ . Para mayor comodidad, escriba $f(x,y)$ para $\zeta(2)\,xy\,\ln(xy)$ . Estos pares $(x,y)$ junto con los correspondientes $m(x,y)$ se enumeran a continuación:
(1) $m(3,7)=110$ con $f(3,7)\approx 105.17$ ,
(2) $m(4,15)=462$ con $f(4,15)\approx 404.10$ ,
(3) $m(4,37)=1386$ con $f(4,37)\approx 1216.57$ ,
(4) $m(4,41)=1386$ con $f(4,41)\approx 1375.79$ ,
(5) $m(4,63)=2310$ con $f(4,63)\approx 2292.08$ ,
(6) $m(8,37)=2772$ con $f(8,37)\approx 2770.64$ ,
(7) $m(8,73)=6270$ con $f(8,73)\approx 6119.19$ ,
(8) $m(11,23)=2310$ con $f(11,23)\approx 2302.82$ ,
(9) $m(11,58)=6930$ con $f(11,58)\approx 6777.82$ ,
(10) $m(14,45)=7410$ con $f(14,45)\approx 6679.75$ ,
(11) $m(19,20)=3990$ con $f(19,20)\approx 3713.05$ ,
(12) $m(21,61)=15510$ con $f(21,61)\approx 15077.6$ ,
(13) $m(22,25)=6090$ con $f(22,25)\approx 5708.67$ ,
(14) $m(28,45)=14820$ con $f(28,45)\approx 14796.1$ ,
(15) $m(35,86)=40590$ con $f(35,86)\approx 39658.0$ ,
(16) $m(41,55)=30030$ con $f(41,55)\approx 28639.4$ ,
(17) $m(61,89)=87780$ con $f(61,89)\approx 76796.6$ y
(18) $m(67,89)=90090$ con $f(67,89)\approx 85270.6$ .
La pareja $(4,15)$ es la que más se desvía de la $xy$ -vs- $f(x,y)$ curva, seguida de $(61,89)$ y $(14,45)$ respectivamente. Originalmente pensé que estos extraordinarios pares $(x,y)$ tendría muchos divisores primos, especialmente primos pequeños, pero aparentemente, los datos indican que los divisores primos de $xy$ son irrelevantes.