|
5
|
|
edited Jan 29 2011 at 7:16 |
Here is an attempt to give a somewhat finer grained view of the distribution. The set of ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}} \subset(0,\frac{1}{2})$ are essentially the values in the first half of the Farey sequence $\lbrace \frac{p}{q} | \gcd(p,q)=1,\ 2p \le q<N\ \rbrace$. This has already been pointed out but I'll give a simple (if less nuanced) justification. Then I'll mention how that sequence is and is not smoothly distributed.
Instead of looking at all the relatively prime pairs $(a,b)$ with $1 \le a,b\le N$ I'll just consider those with $a<b$ since order is irrelevant for the question asked and $(a,b)=(1,1)$ is an extreme outlier. There are non-negative integers $s,t$ with $|as-bt|=1$ and just one such pair with $\sqrt{\frac{s^2+t^2}{a^2+b^2}}<\frac{1}{2}$. Call this This ratio $c(a,b)$. It turns out to be very close to $\frac{t}{s}$. Then $(0,0),(t,s),(a,b)$ and $(t+a,s+b)$ are corners of a long thin parallelogram with area 1 and (thus) no integer points on its boundary or interior. Because the sides are very nearly parallel, the ratio $\sqrt{\frac{s^2+t^2}{a^2+b^2}}$ of their lengths is quite close to $\frac{t}{a}$ and even closer to $\frac{s}{b}$ (in fact they are convergents to the continued fraction for that irrational number). So that set of ratios is quite close to the lower half of the set of fractions :
LATER
For fixed $b$ the discrepency between $\sqrt{\frac{s^2+t^2}{a^2+b^2}}$ and $\frac{s}{b}$ is almost exactly $\frac{1}{b(2b^2+1)}$ for $\frac{1}{b}$ and increases to $\frac{2}{b(4b-1)}$ for $\frac{b-1}{b}$
Let $\mathcal{H}_N=\lbrace \frac {p}{q} |\frac{p}{q}\le \frac{1}{2} ,\gcd(p,q)=1,q \le N \rbrace$ The letter H $\mathcal{H}$ is because this is half a Farey sequence. It is known that $P(N)=|\mathcal{H}_N|=\frac{3N^2}{2\pi^2}+O(N\log N)$. How evenly spaced are these? There are $P \approxeq \frac{0.15}{N^2}$ points in an interval of width $1/2$ so perfectly even spacing would put the kth point at $\frac{k}{2P}\approx\frac{3.3k}{N^2}$. However a fraction $\frac{p}{q}$ with $q$ small will be about $\frac{1}{qN}$ from the next nearest points. Hence the largest point other than $\frac{1}{2}$ is $\frac{1}{2}-\frac{1}{N}$ (replace N by N-1 in the even case) and the smallest point is $\frac{1}{N}$ which seems far from $\frac{3.3}{N^2}$ These empty zones force other points closer together, the first few points are only separated by about $\frac{1}{N^2}$. I can't resist an attempt to put in a picture of Ford Circles. A disk of radius $\frac{1}{q^2}$ is centered at $(\frac{p}{q},\frac{1}{q^2}).$ Disks are either disjoint or tangent. One can see the enforced distance around fractions with small denominators. On the other hand, each disk is put into the largest gap present (albeit not exactly at the center). This is a subtle topic. I'll just mention that a conjecture about the distance (in the $\ell_1$ or $\ell_2$ norm) between the sorted vector of Farey fractions and the evenly spaced vector $[0,1/2P,1/4P,\cdots$ is equivalent to the Riemann Hypothesis.
With the appropriate bin size and placement things might come out fairly even. The chart by the OP uses 100 bins for roughly 608,382 points. As I said, the results should be essentially the same as for $\mathcal{H}_N$. The very first bin is smashed against the y axis but it is below average by 213 and the next two bins are over by about 148 and 30 respectively. It is easier to see that the bin containing $\frac{1}{3}$ ($ 0.330<1/3<0.335$) is deficient from the average by about 95 points (by my calculations) the bin before it is about average but the one after is up by about 68 points. The last bin is under by 33 and the one before it over by 24. My other answer discussed an example made with rounding rather than truncation and a number of bins ($2520=8 \cdot 9 \cdot 5 \cdot 7$) that put simple fractions in the center of a bin. This allowed more choppy behavior.
|
|
|
|
|
4
|
|
edited Jan 29 2011 at 3:05 |
Here is an attempt to give a somewhat finer grained view of the distribution. The set of ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}} \subset(0,\frac{1}{2})$ are essentially the values in the first half of the Farey sequence $\lbrace \frac{p}{q} | \gcd(p,q)=1,\ 2p \le q<N\ \rbrace$. This has already been pointed out but I'll give a simple (if less nuanced) justification. Then I'll mention how that sequence is and is not smoothly distributed.
Instead of looking at all the relatively prime pairs $(a,b)$ with $1 \le a,b\le N$ I'll just consider those with $a<b$ since order is irrelevant for the question asked and $(a,b)=(1,1)$ is an extreme outlier. There are non-negative integers $s,t$ with $|as-bt|=1$ and just one such pair with $\sqrt{\frac{s^2+t^2}{a^2+b^2}}<\frac{1}{2}$. Call this ratio $c(a,b)$. It turns out to be very close to $\frac{t}{s}$. Then $(0,0),(t,s),(a,b)$ and $(t+a,s+b)$ are corners of a long thin parallelogram with area 1 and (thus) no integer points on its boundary or interior. Because the sides are very nearly parallel, the ratio $\sqrt{\frac{s^2+t^2}{a^2+b^2}}\sqrt{\frac{s^2+t^2}{a^2+b^2}}$ of their lengths is quite close to $\frac{t}{a}$ and even closer to $\frac{s}{b}$ (in fact they are convergents to the continued fraction for that irrational number). So that set of ratios is quite close to the lower half of the set of fractions:
Let $\mathcal{H}_N=\lbrace \frac {p}{q} |\frac{p}{q}\le \frac{1}{2} ,\gcd(p,q)=1,q \le N \rbrace$ The letter H is because this is half a Farey sequence. It is known that $P(N)=|\mathcal{H}_N|=\frac{3N^2}{2\pi^2}+O(N\log N)$. How evenly spaced are these? There are $P \approxeq \frac{0.15}{N^2}$ points in an interval of width $1/2$ so perfectly even spacing would put the kth point at $\frac{k}{2P}\approx\frac{3.3k}{N^2}$. However a fraction $\frac{p}{q}$ with $q$ small will be about $\frac{1}{qN}$ from the next nearest points. Hence the largest point other than $\frac{1}{2}$ is $\frac{1}{2}-\frac{1}{N}$ (replace N by N-1 in the even case) and the smallest point is $\frac{1}{N}$ which seems far from $\frac{3.3}{N^2}$ These empty zones force other points closer together, the first few points are only separated by about $\frac{1}{N^2}$. I can't resist an attempt to put in a picture of Ford Circles. A disk of radius $\frac{1}{q^2}$ is centered at $(\frac{p}{q},\frac{1}{q^2}).$ Disks are either disjoint or tangent. One can see the enforced distance around fractions with small denominators. On the other hand, each disk is put into the largest gap present (albeit not exactly at the center). This is a subtle topic. I'll just mention that a conjecture about the distance (in the $\ell_1$ or $\ell_2$ norm) between the sorted vector of Farey fractions and the evenly spaced vector $[0,1/2P,1/4P,\cdots$ is equivalent to the Riemann Hypothesis.
With the appropriate bin size and placement things might come out fairly even. The chart by the OP uses 100 bins for roughly 608,382 points. As I said, the results should be essentially the same as for $\mathcal{H}_N$. The very first bin is smashed against the y axis but it is below average by 213 and the next two bins are over by about 148 and 30 respectively. It is easier to see that the bin containing $\frac{1}{3}$ ($ 0.330<1/3<0.335$) is deficient from the average by about 95 points (by my calculations) the bin before it is about average but the one after is up by about 68 points. The last bin is under by 33 and the one before it over by 24. My other answer discussed an example made with rounding rather than truncation and a number of bins ($2520=8 \cdot 9 \cdot 5 \cdot 7$) that put simple fractions in the center of a bin. This allowed more choppy behavior.
|
|
|
|
|
3
|
|
edited Jan 29 2011 at 1:44 |
Here is an attempt to give a somewhat finer grained view of the distribution.The distribution. The set of ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}} \subset(0,\frac{1}{2})$ are closely clustered quite near a (subset of)the essentially the values in the first half of the Farey sequence $\lbrace \frac{p}{q} | \gcd(p,q)=1,\ 2p \le q<N\ \rbrace$. This has already been pointed out but I'll give a simple (if less nuanced) justification. Then I'll mention how that sequence is and is not smoothly distributed. Instead of looking at all the relatively prime pairs $(a,b)$ with $1 \le a,b\le N$ I'll just consider those with $a<b$ since order is irrelevant for the question asked and $(a,b)=(1,1)$ is an extreme outlier. There are non-negative integers $s,t$ with $|as-bt|=1$ and just one such pair with $\sqrt{\frac{s^2+t^2}{a^2+b^2}}<\frac{1}{2}$. Call this ratio $c(a,b)$.Then the fractions c(a,b)$. It turns out to be very close to $\frac{a}{b}$ \frac{t}{s}$. Then $(0,0),(t,s),(a,b)$ and $\frac{t}{s}$ (t+a,s+b)$ are corners of a long thin parallelogram with area 1 and (thus) no integer points on its boundary or interior. Because the sides are very close togethernearly parallel, $|\frac{a}{b}-\frac{t}{s}|=\frac{1}{bs}$ It turns out that the ratio $c(a,b)$ \sqrt{\frac{s^2+t^2}{a^2+b^2}} of their lengths is quite close to $\frac{t}{a}$. \frac{t}{a}$ and even closer to $\frac{s}{b}$ (in fact they are convergents to the continued fraction for that irrational number). So I'll first need that set of ratios is quite close to discuss the distribution lower half of those values. the set of fractions: Let $\mathcal{H}_M=\lbrace \mathcal{H}_N=\lbrace \frac {p}{q} |\frac{p}{q}\le \frac{1}{2} ,\gcd(p,q)=1,q \le M N \rbrace$ The letter H is because this is half a Farey sequence. It is known that $P(M)=|\mathcal{H}_M|=\frac{3M^2}{2\pi^2}+O(M\log M)$P(N)=|\mathcal{H}_N|=\frac{3N^2}{2\pi^2}+O(N\log N)$. How evenly spaced are these? There are $P \approxeq \frac{0.15}{M^2}$ frac{0.15}{N^2}$ points in an interval of width $1/2$ so perfectly even spacing would put the kth point at $\frac{k}{2P}\approx\frac{3.3k}{M^2}$. \frac{k}{2P}\approx\frac{3.3k}{N^2}$. However a fraction $\frac{p}{q}$ with $q$ small will be about $\frac{1}{qM}$ \frac{1}{qN}$ from the next nearest points. Hence the largest point other than $\frac{1}{2}$ is $\frac{1}{2}-\frac{1}{M}$ \frac{1}{2}-\frac{1}{N}$ (replace M N by M-1 N-1 in the even case) and the smallest point is $\frac{1}{M}$ \frac{1}{N}$ which seems far from $\frac{3.3}{M^2}$ \frac{3.3}{N^2}$ These empty zones force other points closer together, the first few points are only separated by about $\frac{1}{M^2}$. \frac{1}{N^2}$. I can't resist an attempt to put in a picture of Ford Circles. A disk of radius $\frac{1}{q^2}$ is centered at $(\frac{p}{q},\frac{1}{q^2}).$ Disks are either disjoint or tangent. One can see the enforced distance around fractions with small denominators. On the other hand, each disk is put into the largest gap present (albeit not exactly at the center). This is a subtle topic. I'll just mention that a conjecture about the distance (in the $\ell_1$ or $\ell_2$ norm) between the sorted vector of Farey fractions and the evenly spaced vector $[0,1/2P,1/4P,\cdots$ is equivalent to the Riemann Hypothesis. With the appropriate bin size and placement things might be pretty come out fairly even. The chart by the OP uses 100 bins for roughly 608,382 points. Of course that is not for a Farey sequence but for the ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}}$, however As I hope to convince you that said, the two are quite comparable. results should be essentially the same as for $\mathcal{H}_N$. The very first bin is smashed against the y axis but it is below average by 213 and the next two bins are over by about 148 and 30 respectively. It is easier to see that the bin containing $\frac{1}{3}$ ($ 0.330<1/3<0.335$) is deficient from the average by about 95 points (by my calculations) the bin before it is about average but the one after is up by about 68 points. The last bin is under by 33 and the one before it over by 24. My other answer discussed an example made with rounding rather than truncation and a number of bins ($2520=8 \cdot 9 \cdot 5 \cdot 7$) that put simple fractions in the center of a bin. This allowed more choppy behavior. Let me now try to justify my claims above. I think this is accurate but haven't checked every detail, the cases 1/2 and 0/1 are probably a little exceptional: Assume that we are computing the ratios $c(a,b)$ for the relatively prime pairs with $1\le a<b \le N$ Take a fraction $\frac{0}{1} \le \frac{t}{a} \le \frac{1}{2}$ Now consider the points $(a,b)=(a,u+am)$ where $m$ starts at 1 and stops just before $u+am>N$. Here $1 \le u \le a-1$ is either of two numbers (essentially $\pm \frac{1}{t} \mod a$). One will give values $c(a,b)$ approaching $\frac{t}{a}$ from above and the other from below. Including the Bezout cofactors the points are $(a,b,s,t)=(a,u+ma,v+mt,t)$ where $|av-tu|=1$.Note that $|as-bt|=|av+mat-ut-mat|=1$. Thus $|\frac{s}{b}-\frac{t}{a}|=\frac{1}{ab}=\frac{1}{a(ma+u)}$ So it is not surprising that $c(a,b)=\sqrt{\frac{s^2+t^2}{b^2+a^2}}$ has $\frac{t}{a}$ as a best approximation . As $m$ increases the $c(a,b)=c(a,ma+u)$ move towards $\frac{t}{a}$ however each is significantly closer to $c(a,(m-1)a+u)$ than it is to $\frac{t}{a}$ This is only a partial picture but it does indicate some of the observed behavior. $\mathcal{H}_N$ is replaced by about twice as many points (because we allow $\frac{a}{b}$ to be as large as 1 rather than $\frac{1}{2}$). Here $\frac{t}{a}$ has on order of $\frac{2N}{a}$ of the $c(a,b)$ close to it, about half on each side. In the case $\mathcal{H}_{100}$ there are 1152 points. Here are the statistics of how the $c(a,b)$ were distributed. The entry [[4,3], 11] means that there were 11 points with 4 below and 3 above. [[0, 0], 506], [[1, 0], 258], [[0, 1], 252], [[1, 1], 202], [[2, 1], 60], [[2, 2], 56], [[1, 2], 42], [[3, 3], 25], [[3, 2], 24], [[2, 3], 13], [[4, 3], 11], [[4, 4], 11], [[5, 5], 9], [[3, 4], 6], [[5, 4], 5], [[8, 8], 4], [[7, 7], 4], [[4, 5], 4], [[6, 6], 3], [[6, 5], 3], [[10, 10], 2], [[7, 6], 2], [[5, 6], 2], [[12, 11], 2], [[6, 7], 2], [[9, 9], 2], [[19, 19], 2], [[9, 8], 1], [[0, 99], 1], [[49, 0], 1], [[8, 7], 1], [[13, 13], 1], [[0, 49], 1], [[14, 13], 1], [[16, 15], 1], [[11, 10], 1], [[13, 14], 1], [[33, 32], 1], [[24, 24], 1].
|
|
|
|
2
|
|
edited Jan 28 2011 at 17:32 |
Here is an attempt to give a somewhat finer grained view of the distribution.The set of ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}} \subset(0,\frac{1}{2})$ are closely clustered quite near a (subset of)the values in the Farey sequence $\lbrace \frac{p}{q} | \gcd(p,q)=1,\ 2p \le q<N\ \rbrace$.
Instead of looking at all the relatively prime pairs $(a,b)$ with $1 \le a,b\le N$ I'll just consider those with $a<b$ since order is irrelevant for the question asked and $(a,b)=(1,1)$ is an extreme outlier. There are non-negative integers $s,t$ with $|as-bt|=1$ and just one such pair with $\sqrt{\frac{s^2+t^2}{a^2+b^2}}<\frac{1}{2}$. Call this ratio $c(a,b)$.Then the fractions $\frac{a}{b}$ and $\frac{t}{s}$ are very close together, $|\frac{a}{b}-\frac{t}{s}|=\frac{1}{bs}$ It turns out that $c(a,b)$ is close to $\frac{t}{a}$. So I'll first need to discuss the distribution of those values.
Let $\mathcal{H}_M=\lbrace \frac {p}{q} |\frac{p}{q}\le \frac{1}{2} ,\gcd(p,q)=1,q \le M \rbrace$ The letter H is because this is half a Farey sequence. It is known that $P(M)=|\mathcal{H}_M|=\frac{3M^2}{2\pi^2}+O(M\log M)$. How evenly spaced are these? There are $P \approxeq \frac{0.15}{M^2}$ points in an interval of width $1/2$ so perfectly even spacing would put the kth point at $\frac{k}{2P}\approx\frac{3.3k}{M^2}$. However a fraction $\frac{p}{q}$ with $q$ small will be about $\frac{1}{qM}$ from the next nearest points. Hence the largest point other than $\frac{1}{2}$ is $\frac{1}{2}-\frac{1}{M}$ (replace M by M-1 in the even case) and the smallest point is $\frac{1}{M}$ which seems far from $\frac{3.3}{M^2}$ These empty zones force other points closer together, the next first few points are only separated by about $\frac{1}{M^2}$. I can't resist an attempt to put in a picture of Ford Circles. A disk of radius $\frac{1}{q^2}$ is centered at $(\frac{p}{q},\frac{1}{q^2}).$ Disks are either disjoint or tangent. One can see the enforced distance around fractions with small denominators. On the other hand, each disk is put into the largest gap present (albeit not exactly at the center). This is a subtle topic. I'll just mention that a conjecture about the distance (in the $\ell_1$ or $\ell_2$ norm) between the sorted vector of Farey fractions and the evenly spaced vector $[0,1/2P,1/4P,\cdots$ is equivalent to the Riemann Hypothesis.
With the appropriate bin size things might be pretty even. The chart by the OP uses 100 bins for roughly 608,382 points. Of course that is not for a Farey sequence but for the ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}}$, however I hope to convince you that the two are quite comparable. The very first bin is smashed against the y axis but it is below average by 213 and the next two bins are over by about 148 and 30 respectively. It is easier to see that the bin containing $\frac{1}{3}$ ($ 0.330<1/3<0.335$) is deficient from the average by about 95 points (by my calculations) the bin before it is about average but the one after is up by about 68 points. The last bin is under by 33 and the one before it over by 24. My other answer discussed an example made with rounding rather than truncation and a number of bins ($2520=8 \cdot 9 \cdot 5 \cdot 7$) that put simple fractions in the center of a bin. This allowed more choppy behavior.
Let me now try to justify my claims above. I think this is accurate but haven't checked every detail, the cases 1/2 and 0/1 are probably a little exceptional: Assume that we are computing the ratios $c(a,b)$ for the relatively prime pairs with $1\le a<b \le N$ Take a fraction $\frac{0}{1} \le \frac{t}{a} \le \frac{1}{2}$ Now consider the points $(a,b)=(a,u+am)$ where $m$ starts at 1 and stops just before $u+am>N$. Here $1 \le u \le a-1$ is either of two numbers (essential essentially $\pm \frac{1}{t} \mod a$). One will give values $c(a,b)$ approaching $\frac{t}{a}$ from above and the other from below. Including the Bezout cofactors the points are $(a,b,s,t)=(a,u+ma,v+mt,t)$ where $|av-tu|=1$.Note that $|as-bt|=|av+mat-ut-mat|=1$. Thus $|\frac{s}{b}-\frac{t}{a}|=\frac{1}{ab}=\frac{1}{a(ma+u)}$ So it is not surprising that $c(a,b)=\sqrt{\frac{s^2+t^2}{b^2+a^2}}$ has $\frac{t}{a}$ as a best approximation . As $m$ increases the $c(a,b)=c(a,ma+u)$ move towards $\frac{t}{a}$ however each is significantly closer to $c(a,(m-1)a+u)$ than it is to $\frac{t}{a}$
This is only a partial picture but it does indicate some of the observed behavior. $\mathcal{H}_N$ is replaced by about twice as many points (because we allow $\frac{a}{b}$ to be as large as 1 rather than $\frac{1}{2}$). Here $\frac{t}{a}$ has on order of $\frac{2N}{a}$ of the $c(a,b)$ close to it, about half on each side. In the case $\mathcal{H}_{100}$ there are 1152 points. Here are the statistics of how the $c(a,b)$ were distributed. The entry [[4,3], 11] means that there were 11 points with 4 below and 3 above.
[[0, 0], 506], [[1, 0], 258], [[0, 1], 252], [[1, 1], 202], [[2, 1], 60], [[2, 2], 56], [[1, 2], 42], [[3, 3], 25], [[3, 2], 24], [[2, 3], 13], [[4, 3], 11], [[4, 4], 11], [[5, 5], 9], [[3, 4], 6], [[5, 4], 5], [[8, 8], 4], [[7, 7], 4], [[4, 5], 4], [[6, 6], 3], [[6, 5], 3], [[10, 10], 2], [[7, 6], 2], [[5, 6], 2], [[12, 11], 2], [[6, 7], 2], [[9, 9], 2], [[19, 19], 2], [[9, 8], 1], [[0, 99], 1], [[49, 0], 1], [[8, 7], 1], [[13, 13], 1], [[0, 49], 1], [[14, 13], 1], [[16, 15], 1], [[11, 10], 1], [[13, 14], 1], [[33, 32], 1], [[24, 24], 1].
|
|
|
|
|
1
|
|
answered Jan 28 2011 at 17:15 |
Here is an attempt to give a somewhat finer grained view of the distribution.The set of ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}} \subset(0,\frac{1}{2})$ are closely clustered quite near a (subset of)the values in the Farey sequence $\lbrace \frac{p}{q} | \gcd(p,q)=1,\ 2p \le q<N\ \rbrace$.
Instead of looking at all the relatively prime pairs $(a,b)$ with $1 \le a,b\le N$ I'll just consider those with $a<b$ since order is irrelevant for the question asked and $(a,b)=(1,1)$ is an extreme outlier. There are non-negative integers $s,t$ with $|as-bt|=1$ and just one such pair with $\sqrt{\frac{s^2+t^2}{a^2+b^2}}<\frac{1}{2}$. Call this ratio $c(a,b)$.Then the fractions $\frac{a}{b}$ and $\frac{t}{s}$ are very close together, $|\frac{a}{b}-\frac{t}{s}|=\frac{1}{bs}$ It turns out that $c(a,b)$ is close to $\frac{t}{a}$. So I'll first need to discuss the distribution of those values.
Let $\mathcal{H}_M=\lbrace \frac {p}{q} |\frac{p}{q}\le \frac{1}{2} ,\gcd(p,q)=1,q \le M \rbrace$ The letter H is because this is half a Farey sequence. It is known that $P(M)=|\mathcal{H}_M|=\frac{3M^2}{2\pi^2}+O(M\log M)$. How evenly spaced are these? There are $P \approxeq \frac{0.15}{M^2}$ points in an interval of width $1/2$ so perfectly even spacing would put the kth point at $\frac{k}{2P}\approx\frac{3.3k}{M^2}$. However a fraction $\frac{p}{q}$ with $q$ small will be about $\frac{1}{qM}$ from the next nearest points. Hence the largest point other than $\frac{1}{2}$ is $\frac{1}{2}-\frac{1}{M}$ (replace M by M-1 in the even case) and the smallest point is $\frac{1}{M}$ which seems far from $\frac{3.3}{M^2}$ These empty zones force other points closer together, the next few points are only separated by about $\frac{1}{M^2}$. I can't resist an attempt to put in a picture of Ford Circles. A disk of radius $\frac{1}{q^2}$ is centered at $(\frac{p}{q},\frac{1}{q^2}).$ Disks are either disjoint or tangent. One can see the enforced distance around fractions with small denominators. On the other hand, each disk is put into the largest gap present (albeit not exactly at the center). This is a subtle topic. I'll just mention that a conjecture about the distance (in the $\ell_1$ or $\ell_2$ norm) between the sorted vector of Farey fractions and the evenly spaced vector $[0,1/2P,1/4P,\cdots$ is equivalent to the Riemann Hypothesis.
With the appropriate bin size things might be pretty even. The chart by the OP uses 100 bins for roughly 608,382 points. Of course that is not for a Farey sequence but for the ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}}$, however I hope to convince you that the two are quite comparable. The very first bin is smashed against the y axis but it is below average by 213 and the next two bins are over by about 148 and 30 respectively. It is easier to see that the bin containing $\frac{1}{3}$ ($ 0.330<1/3<0.335$) is deficient from the average by about 95 points (by my calculations) the bin before it is about average but the one after is up by about 68 points. The last bin is under by 33 and the one before it over by 24. My other answer discussed an example made with rounding rather than truncation and a number of bins ($2520=8 \cdot 9 \cdot 5 \cdot 7$) that put simple fractions in the center of a bin. This allowed more choppy behavior.
Let me now try to justify my claims above. I think this is accurate but haven't checked every detail, the cases 1/2 and 0/1 are probably a little exceptional: Assume that we are computing the ratios $c(a,b)$ for the relatively prime pairs with $1\le a<b \le N$ Take a fraction $\frac{0}{1} \le \frac{t}{a} \le \frac{1}{2}$ Now consider the points $(a,b)=(a,u+am)$ where $m$ starts at 1 and stops just before $u+am>N$. Here $1 \le u \le a-1$ is either of two numbers (essential $\pm \frac{1}{t} mod a$). One will give values $c(a,b)$ approaching $\frac{t}{a}$ from above and the other from below. Including the Bezout cofactors the points are $(a,b,s,t)=(a,u+ma,v+mt,t)$ where $|av-tu|=1$.Note that $|as-bt|=|av+mat-ut-mat|=1$. Thus $|\frac{s}{b}-\frac{t}{a}|=\frac{1}{ab}=\frac{1}{a(ma+u)}$ So it is not surprising that $c(a,b)=\sqrt{\frac{s^2+t^2}{b^2+a^2}}$ has $\frac{t}{a}$ as a best approximation . As $m$ increases the $c(a,b)=c(a,ma+u)$ move towards $\frac{t}{a}$ however each is significantly closer to $c(a,(m-1)a+u)$ than it is to $\frac{t}{a}$
This is only a partial picture but it does indicate some of the observed behavior. $\mathcal{H}_N$ is replaced by about twice as many points (because we allow $\frac{a}{b}$ to be as large as 1 rather than $\frac{1}{2}$). Here $\frac{t}{a}$ has on order of $\frac{2N}{a}$ of the $c(a,b)$ close to it, about half on each side. In the case $\mathcal{H}_{100}$ there are 1152 points. Here are the statistics of how the $c(a,b)$ were distributed. The entry [[4,3], 11] means that there were 11 points with 4 below and 3 above.
[[0, 0], 506], [[1, 0], 258], [[0, 1], 252], [[1, 1], 202], [[2, 1], 60], [[2, 2], 56], [[1, 2], 42], [[3, 3], 25], [[3, 2], 24], [[2, 3], 13], [[4, 3], 11], [[4, 4], 11], [[5, 5], 9], [[3, 4], 6], [[5, 4], 5], [[8, 8], 4], [[7, 7], 4], [[4, 5], 4], [[6, 6], 3], [[6, 5], 3], [[10, 10], 2], [[7, 6], 2], [[5, 6], 2], [[12, 11], 2], [[6, 7], 2], [[9, 9], 2], [[19, 19], 2], [[9, 8], 1], [[0, 99], 1], [[49, 0], 1], [[8, 7], 1], [[13, 13], 1], [[0, 49], 1], [[14, 13], 1], [[16, 15], 1], [[11, 10], 1], [[13, 14], 1], [[33, 32], 1], [[24, 24], 1].
|
|
|
