3 ms·

>> Suppose that I can find some lists of numbers whose sums of square roots are equal for the first ten million decimal points and then start being different W

>> Suppose that I can find some lists of numbers whose sums of square roots are equal for the first ten million decimal points and then start being different Would have been nice to add an example of such list in the blog, I wonder how short that list can be. Also, how important is this in practice? The algorithms using this comparison could handle the 3 cases with a tolerance (larger, smaller, undecided)?

dmurray 5y ago
I expect not very important in practice, because 1. We've settled on using IEEE 754 floating point numbers, and all their tolerance quirks, in practice, and still the bridges don't fall down 2. The author describes it as a little-studied field where "most of the people who would be good at working on this are doing something more useful instead" But still, useless pure-maths distractions have a way of yielding results in unexpected fields. Maybe, as the author hints, a solution to this problem would bring us some information-theory insights and some new methods for cryptography or compression or whatever else.
Someone 5y ago
Very short, expressed in number of items in the lists. Once N is large enough, these two single-item lists have that: First list: (N) Second list: (N + 1) N = 10^10^15 is large enough for that. I think you can construct much smaller examples by looking at Pythagorean triples. Since 3² + 4² = 5² and 5² + 12² = 13², the lists (9k, 16k, 169k) and (25k, 144k, 25k) have the same sum of square roots (22√k) for all k. Subtract one from one of the numbers, and you’ll have a close match, say with error e. Do the same for a second pair of Pythagorean triples, giving you an error of f. Compute a good rational approximation p/q of e/f, and linearly combine the pairs of sets to get any arbitrary small difference (edit: that construction works starting with any two sets of two sets of numbers) And I don’t think there is an “in practice” for this problem. When do you ever have to make this computation? If ever, does it matter if your code fails on a tiny fraction of all inputs?

dmurray 5y ago

I expect not very important in practice, because 1. We've settled on using IEEE 754 floating point numbers, and all their tolerance quirks, in practice, and still the bridges don't fall down 2. The author describes it as a little-studied field where "most of the people who would be good at working on this are doing something more useful instead" But still, useless pure-maths distractions have a way of yielding results in unexpected fields. Maybe, as the author hints, a solution to this problem would bring us some information-theory insights and some new methods for cryptography or compression or whatever else.

Someone 5y ago

Very short, expressed in number of items in the lists. Once N is large enough, these two single-item lists have that: First list: (N) Second list: (N + 1) N = 10^10^15 is large enough for that. I think you can construct much smaller examples by looking at Pythagorean triples. Since 3² + 4² = 5² and 5² + 12² = 13², the lists (9k, 16k, 169k) and (25k, 144k, 25k) have the same sum of square roots (22√k) for all k. Subtract one from one of the numbers, and you’ll have a close match, say with error e. Do the same for a second pair of Pythagorean triples, giving you an error of f. Compute a good rational approximation p/q of e/f, and linearly combine the pairs of sets to get any arbitrary small difference (edit: that construction works starting with any two sets of two sets of numbers) And I don’t think there is an “in practice” for this problem. When do you ever have to make this computation? If ever, does it matter if your code fails on a tiny fraction of all inputs?