[seqfan] Re: Worry about old sequence, A030077, paths in K_n

[Tim Peters]

Resurrecting this seeming distraction because herein lies an
educational cautionary tale:

On Mon, Apr 4, 2022 at 9:48 PM David Applegate <david at bcda.us> wrote:
> Yes. My comment about sums of square roots was not relevant to this
> sequence - I reacted to "distinct lengths of paths" and approaches that
> were using floating point computations to check for distinct paths, and
> recalled that in some cases (specifically euclidean lengths of paths
> between points with integer coordinates) there is no reasonable bound on
> the precision needed to determine whether one path is shorter or longer
> than another. That was not relevant for two reasons: first, even for
> euclidean paths, the question "do these two paths have the same length"
> is easier than "which path is longer" (but still non-trivial, and not
> based on floating point), and second, the points in this case are evenly
> spaced on the unit circle, not integer coordinates.
>
> However, I think the concern was valid - using floating point
> computations to distinguish "equals" from "not equals" is sometimes
> possible, but require careful bounds on the possible errors, and can be
> surprisingly tricky. In this case, others were already doing careful
> processing that wasn't based on floating-point assumptions, so it was an
> unnecessary distraction.

And, as things turned out, using native double-precision (64-bit)
floats eventually _did_ give bad results, but not until reaching n=26.
At that value of n, there are:

1852482996 chord multisets to consider
1494584 of which are inadmissible
the remaining 1850988412 are all realizable
and all have distinct lengths

But comparing lengths with native doubles thought 45 lengths were
duplicates - they compared equal to within 26 ulp, and one pair within
5 ulp. False alarms!

I thought analysis with PSLQ would save me from that, but I was wrong.
PSLQ isn't trying to find all "close to 0" combinations, just "the
best" one. At n=26, the best close-to-0 combination it found involves
7 of the possible chord lengths. In fact, it's a true identity. But
take any one of those 7 chord lengths out of the base vector input to
PSLQ, and the closest-to-equal false alarm is also excluded, because
it also requires all 7 of those chords. If PSLQ is blinded to one,
it's blinded to both.

Most of the rest of the false alarms can be avoided by tightening the
bound on what "equal" means, but it doesn't matter - it only takes one
counterexample to break the approach.

So, ya, "surprisingly tricky" applies. OTOH, code slinging cyclotomic
polynomials is more delicate to code, and much slower to run. I still
find floats useful to weed out the "obviously nowhere close to equal"
cases. But now there's a mix of approaches, and so the code gets
harder to follow. So, ya, "surprisingly tricky" will always apply :-)