[math-fun] points on NxN grid with no repeated distance (problem posed by Keith F. Lynch)
Keith F. Lynch <kfl at KeithLynch.net> wrote: How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal? WDS: Let F(N) denote this quantity. UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N. STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214. LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works. CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
See P.~Erd\H{o}s \& Richard K.~Guy, Distinct distances between lattice points, {\it Elem.\ Math.} {\bf 25}(1970) 121--123; {\it MR} {\bf 43} \#7406; {\it Zbl} {\bf 222}.10053; {\it RZh} 1971 5A153. On Wed, 13 Apr 2016, Warren D Smith wrote:
Keith F. Lynch <kfl at KeithLynch.net> wrote: How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal?
WDS: Let F(N) denote this quantity.
UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N.
STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214.
LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works.
CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
http://www.azspcs.net/Contest/PointPacking/FinalReport http://demonstrations.wolfram.com/NoRepeatedDistances/ has some best known solutions. On Wed, Apr 13, 2016 at 3:53 PM, rkg <rkg@ucalgary.ca> wrote:
See
P.~Erd\H{o}s \& Richard K.~Guy, Distinct distances between lattice points, {\it Elem.\ Math.} {\bf 25}(1970) 121--123; {\it MR} {\bf 43} \#7406; {\it Zbl} {\bf 222}.10053; {\it RZh} 1971 5A153.
On Wed, 13 Apr 2016, Warren D Smith wrote:
Keith F. Lynch <kfl at KeithLynch.net> wrote:
How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal?
WDS: Let F(N) denote this quantity.
UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N.
STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214.
LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works.
CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This question arose when Keith Lynch was saying that it is hard to find information about math problems. As several people observed, if you can work out a number sequence that describes the first few terms you can look it up in the OEIS. For the distinct distances in a grid question, see https://oeis.org/193838 and the new A271490. If you know of results that are not mentioned in those entries, please add them! Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Apr 14, 2016 at 11:29 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
http://www.azspcs.net/Contest/PointPacking/FinalReport
http://demonstrations.wolfram.com/NoRepeatedDistances/
has some best known solutions.
On Wed, Apr 13, 2016 at 3:53 PM, rkg <rkg@ucalgary.ca> wrote:
See
P.~Erd\H{o}s \& Richard K.~Guy, Distinct distances between lattice points, {\it Elem.\ Math.} {\bf 25}(1970) 121--123; {\it MR} {\bf 43} \#7406; {\it Zbl} {\bf 222}.10053; {\it RZh} 1971 5A153.
On Wed, 13 Apr 2016, Warren D Smith wrote:
Keith F. Lynch <kfl at KeithLynch.net> wrote:
How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal?
WDS: Let F(N) denote this quantity.
UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N.
STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214.
LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works.
CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Generally the results from Al Zimmermann's contests tend to be empirical and not definitive, so don't mesh well with the OEIS sequences. It would be really nice if there was a general repository of "best results" for problems such as these that people could contribute to, rather than having random pages collected by random people all over the web on various problems. I'm not sure how this would work; something like a cross between Project Euler, Al Zimmermann's Programming Contests, and OEIS. -tom On Thu, Apr 14, 2016 at 9:03 AM, Neil Sloane <njasloane@gmail.com> wrote:
This question arose when Keith Lynch was saying that it is hard to find information about math problems. As several people observed, if you can work out a number sequence that describes the first few terms you can look it up in the OEIS.
For the distinct distances in a grid question, see https://oeis.org/193838 and the new A271490.
If you know of results that are not mentioned in those entries, please add them!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Apr 14, 2016 at 11:29 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
http://www.azspcs.net/Contest/PointPacking/FinalReport
http://demonstrations.wolfram.com/NoRepeatedDistances/
has some best known solutions.
On Wed, Apr 13, 2016 at 3:53 PM, rkg <rkg@ucalgary.ca> wrote:
See
P.~Erd\H{o}s \& Richard K.~Guy, Distinct distances between lattice points, {\it Elem.\ Math.} {\bf 25}(1970) 121--123; {\it MR} {\bf 43} \#7406; {\it Zbl} {\bf 222}.10053; {\it RZh} 1971 5A153.
On Wed, 13 Apr 2016, Warren D Smith wrote:
Keith F. Lynch <kfl at KeithLynch.net> wrote:
How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal?
WDS: Let F(N) denote this quantity.
UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N.
STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214.
LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works.
CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
as someone whose hundreds of math magic pages are included in those "random pages of random people", i agree it would be nice to have a central location for such things. plus, some mechanism to contribute for those of us more predisposed to asking interesting questions than answering them. erich
On Apr 14, 2016, at 12:17 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Generally the results from Al Zimmermann's contests tend to be empirical and not definitive, so don't mesh well with the OEIS sequences. It would be really nice if there was a general repository of "best results" for problems such as these that people could contribute to, rather than having random pages collected by random people all over the web on various problems.
I'm not sure how this would work; something like a cross between Project Euler, Al Zimmermann's Programming Contests, and OEIS.
-tom
On Thu, Apr 14, 2016 at 9:03 AM, Neil Sloane <njasloane@gmail.com> wrote:
This question arose when Keith Lynch was saying that it is hard to find information about math problems. As several people observed, if you can work out a number sequence that describes the first few terms you can look it up in the OEIS.
For the distinct distances in a grid question, see https://oeis.org/193838 and the new A271490.
If you know of results that are not mentioned in those entries, please add them!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Apr 14, 2016 at 11:29 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
http://www.azspcs.net/Contest/PointPacking/FinalReport
http://demonstrations.wolfram.com/NoRepeatedDistances/
has some best known solutions.
On Wed, Apr 13, 2016 at 3:53 PM, rkg <rkg@ucalgary.ca> wrote:
See
P.~Erd\H{o}s \& Richard K.~Guy, Distinct distances between lattice points, {\it Elem.\ Math.} {\bf 25}(1970) 121--123; {\it MR} {\bf 43} \#7406; {\it Zbl} {\bf 222}.10053; {\it RZh} 1971 5A153.
On Wed, 13 Apr 2016, Warren D Smith wrote:
Keith F. Lynch <kfl at KeithLynch.net> wrote:
How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal?
WDS: Let F(N) denote this quantity.
UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N.
STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214.
LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works.
CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Tom Rokicki wrote:
Generally the results from Al Zimmermann's contests tend to be empirical and not definitive, so don't mesh well with the OEIS sequences. It would be really nice if there was a general repository of "best results" for problems such as these that people could contribute to, rather than having random pages collected by random people all over the web on various problems.
Maybe an Online Encyclopedia of Interval Sequences, which can include lower and upper bounds if exact values are unknown? Then, you can see whether two sequences ([a_n, b_n]) and ([c_n, d_n]) are plausibly the same by checking that a_n \leq d_n and c_n \leq b_n for all n. There is, of course, no requirement that the terms be integers. So you could look up the zeta function by evaluating upper and lower bounds for: \sum_i(1 / i^n) for a few values of n and entering the information into the search bar. At no point do you ever need to know that this is called the Riemann zeta function, or even know the formula (you may have found these values by Monte Carlo testing whether n random integers are coprime!). Best wishes, Adam P. Goucher
P.~Erd\H{o}s \& Richard K.~Guy, Distinct distances between lattice points, {\it Elem.\ Math.} {\bf 25}(1970) 121--123; {\it MR} {\bf 43} \#7406; {\it Zbl} {\bf 222}.10053; {\it RZh} 1971 5A153. --Oh. This article by Erdos+Guy did the same stuff I did in my math-fun post only they did it 45 years earlier. Except for my conjectured lower bound N^(1-o(1)). My suggested method for proving that conjecture depends on methods which I believe did not yet exist in 1970, and actually may not even quite exist now. But I think it may well be possible to prove it with more work, perhaps via a variant of the Rodl "nibble" and/or Spencer "randomized greedy" techniques I mentioned to handle the missing final stage of the argument. Recommend investigating. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Here is a different proof that N^(2/3-o(1)) points are achievable: point-adding algorithm. Simply add points to our set one at a time, totally arbitrarily so long as the new point does not cause a distance repetition. Suppose we have a point set with P points and no repeated distances. In that case, there are (P-1)*P/2 used (and hence forbidden for further use) distances. Each current point can be regarded as having "rings" (concentric circles) drawn around it, at forbidden distances. All points we add in the future must NOT lie on any of those rings. The cardinality of any one ring is N^o(1). The total number of forbidden points at a moment when current set has P points, is therefore <=P^3 * N^o(1). So we can keep adding points until P^3 * N^o(1) >= N^2 - P. Hence we can, and always will, achieve P = N^(2/3-o(1)). QED. There is tremendous (indeed total) freedom of choice in this method. The question is how best to exploit it to do better, and how much better is possible. For example, you could in this way get a set with N^0.666 points, then do it again to get a DISJOINT set with N^0.666 points, and so on, thus obtaining N^1.333 disjoint subsets of the NxN grid, each with N^0.666 points, with each subset by itself having no repeated distances (for any large-enough N). Another example: One could in this way get a set with N^0.666 points, with no repeated distances, and also no short distances (less than N^0.666), and also forbidding the N^0.666 distances whose squares have the most representations as sums of two squares. Here is a 1-dimensional problem which might have some relevance: What is the largest subset of {1,2,3,...,N} such that all pairwise differences, are prime? (Might make a good programming contest...) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
{1,3,6} , no? Christoph Originalnachricht Von: Warren D Smith Gesendet: Freitag, 15. April 2016 20:53 An: math-fun Antwort an: math-fun Betreff: Re: [math-fun] points on NxN grid with no repeated distance (problem posed by Keith F. Lynch) Here is a different proof that N^(2/3-o(1)) points are achievable: point-adding algorithm. Simply add points to our set one at a time, totally arbitrarily so long as the new point does not cause a distance repetition. Suppose we have a point set with P points and no repeated distances. In that case, there are (P-1)*P/2 used (and hence forbidden for further use) distances. Each current point can be regarded as having "rings" (concentric circles) drawn around it, at forbidden distances. All points we add in the future must NOT lie on any of those rings. The cardinality of any one ring is N^o(1). The total number of forbidden points at a moment when current set has P points, is therefore <=P^3 * N^o(1). So we can keep adding points until P^3 * N^o(1) >= N^2 - P. Hence we can, and always will, achieve P = N^(2/3-o(1)). QED. There is tremendous (indeed total) freedom of choice in this method. The question is how best to exploit it to do better, and how much better is possible. For example, you could in this way get a set with N^0.666 points, then do it again to get a DISJOINT set with N^0.666 points, and so on, thus obtaining N^1.333 disjoint subsets of the NxN grid, each with N^0.666 points, with each subset by itself having no repeated distances (for any large-enough N). Another example: One could in this way get a set with N^0.666 points, with no repeated distances, and also no short distances (less than N^0.666), and also forbidding the N^0.666 distances whose squares have the most representations as sums of two squares. Here is a 1-dimensional problem which might have some relevance: What is the largest subset of {1,2,3,...,N} such that all pairwise differences, are prime? (Might make a good programming contest...) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 4/15/16, Warren D Smith <warren.wds@gmail.com> wrote:
Here is a different proof that N^(2/3-o(1)) points are achievable: point-adding algorithm.
Simply add points to our set one at a time, totally arbitrarily so long as the new point does not cause a distance repetition. Suppose we have a point set with P points and no repeated distances. In that case, there are (P-1)*P/2 used (and hence forbidden for further use) distances. Each current point can be regarded as having "rings" (concentric circles) drawn around it, at forbidden distances. All points we add in the future must NOT lie on any of those rings. The cardinality of any one ring is N^o(1). The total number of forbidden points at a moment when current set has P points, is therefore <=P^3 * N^o(1). So we can keep adding points until P^3 * N^o(1) >= N^2 - P. Hence we can, and always will, achieve P = N^(2/3-o(1)). QED.
--Sorry; that proof had a flaw. Just putting new point at a place not on any rings, is not good enough. It also must avoid all bisecting lines for pairs of previous points. Such a line could have cardinality as great as N. However random such lines have cardinality of order 1, and on average of order logN.
participants (8)
-
Adam P. Goucher -
Ed Pegg Jr -
Erich Friedman -
Neil Sloane -
Pacher Christoph -
rkg -
Tom Rokicki -
Warren D Smith