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

Tue Apr 5 04:48:48 CEST 2022

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.

-Dave

On 4/4/2022 12:33 AM, Brendan McKay via SeqFan wrote:

> What you are both missing is that the chord lengths are not square 
> roots of integers.
>
> The problem of comparing weighted sums of square roots is completely 
> different from the problem of comparing weighted sums of sines, even 
> though they might coincide in some simple cases.
>
> Now I have found that there are paths with different multisets but the 
> same length for n=18 and (subject to a conjecture) also for n=20.
>
> Brendan.
>
> On 4/4/2022 2:17 pm, israel at math.ubc.ca wrote:
>> Maybe what you're missing is the word "squarefree".  Without it, you do
>> have "trivial" equivalences, for example 2*sqrt(x) = sqrt(4*x) (which
>> is exactly what gives your relation between the diagonal and edge of 
>> a hexagon).
>>
>> Cheers,
>> Robert
>>
>> On Apr 3 2022, Allan Wechsler wrote:
>>
>>> I must be missing something very dumb. If the different diagonals 
>>> are all
>>> incommensurate then why are we doing high-precision floating point
>>> arithmetic at all, and why are we worrying about whether two "cyclic
>>> polylines" might or might not be equal? If the diagonals are
>>> incommensurate, all we need to know is the number of each kind of 
>>> diagonal.
>>> That can't be right; there must be linear equivalences. (Note, for 
>>> example,
>>> that the long diagonal of a hexagon is exactly twice an edge.)
>>>
>>> On Sun, Apr 3, 2022 at 3:16 PM <israel at math.ubc.ca> wrote:
>>>
>>>> There are no nontrivial equivalences: the square roots of squarefree
>>>> integers are linearly independent over the rationals. See e.g.
>>>>
>>>>
>>>>
>>>> https://aus01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fqchu.wordpress.com%2F2009%2F07%2F02%2Fsquare-roots-have-no-unexpected-linear-relationships%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335528344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=zEbyQxBbGRtras%2FnSCqOLheop45Nj0EU%2BE4eOpEDnHg%3D&reserved=0 
>>>>
>>>>
>>>> Cheers,
>>>> Robert
>>>>
>>>> On Apr 3 2022, Allan Wechsler wrote:
>>>>
>>>> > Are there any good examples of nontrivial equivalences? I'm 
>>>> thinking > that we might be able to *characterize* nontrivial 
>>>> equivalences, and > thus be able to prove two paths to be unequal 
>>>> in a sort of > "combinatorial" way, without resorting to extended 
>>>> arithmetic.
>>>> >
>>>> >On Sat, Apr 2, 2022 at 3:03 PM Sean A. Irvine <sairvin at gmail.com> 
>>>> wrote:
>>>> >
>>>> >> By the way, my code is using computable reals not 
>>>> floating-point, but
>>>> >> it still faces the problem of deciding equality. I've been using 50
>>>> >> decimal digits for this problem. I could easily rerun with higher
>>>> >> precision, but I would like to remove the need for the 
>>>> approximation
>>>> >> altogether.
>>>> >>
>>>> >> Sean.
>>>> >>
>>>> >>
>>>> >> On Sun, 3 Apr 2022 at 02:04, David Applegate <david at bcda.us> wrote:
>>>> >>
>>>> >> > I worry about using floating point (extended or not) to check if
>>>> >> > different sums of square roots are equal or not. Using finite
>>>> >> > precision for this is extremely tricky This is a notoriously hard
>>>> >> > problem in general. For example, to see that
>>>> >> > sqrt(7)+sqrt(14)+sqrt(39)+sqrt(70)+sqrt(72)+sqrt(76)+sqrt(85) !=
>>>> >> > sqrt(13)+sqrt(16)+sqrt(55)+sqrt(67)+sqrt(73)+sqrt(79) you already
>>>> need
>>>> >> > more than double-precision floating point (their difference is
>>>> 10^-19,
>>>> >> > see
>>>> >> >
>>>> >> >
>>>> >>
>>>> >>
>>>> >>
>>>>
>>>>
>>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.156.3838%26rep%3Drep1%26type%3Dpdf&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335528344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=lnCKU1v%2B6WrdHDLlpaKGnhHaOHfrsKTyZ4ns0vYTJjk%3D&reserved=0 
>>>>
>>>> >> > ). There is a randomized polynomial time algorithm for testing 
>>>> >> > equality, but it isn't just compute the result to enough 
>>>> precision.
>>>> >> >
>>>> >> > Some links with additional information:
>>>> >> >
>>>> >> >
>>>> >>
>>>> >>
>>>> >>
>>>>
>>>>
>>>> https://aus01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fcstheory.stackexchange.com%2Fquestions%2F79%2Fproblems-between-p-and-npc%2F4010%234010&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335528344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=a9gS028aOANdhjF9lr1h9A986ytoujnLcSqy7QCfrI0%3D&reserved=0 
>>>>
>>>> >> > 
>>>> https://aus01.safelinks.protection.outlook.com/?url=https%3A%2F%2Ftopp.openproblem.net%2Fp33&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335528344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=QQ11fCL1VD7qlxBKtRtJaa2kOXPoS%2BouSl5dHog%2FKiQ%3D&reserved=0
>>>> >> >
>>>> >> >
>>>> >>
>>>> >>
>>>> >>
>>>>
>>>>
>>>> https://aus01.safelinks.protection.outlook.com/?url=https%3A%2F%2Frefubium.fu-berlin.de%2Fbitstream%2Fhandle%2Ffub188%2F18449%2F1993-13.pdf%3Bjsessionid%3D89F489131478714C98250CFA34AFBFE7%3Fsequence%3D1&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335528344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=TLVxbMpOnpnEW6Echc1nE4zqRdzZz7NDd2rnPVcfFDg%3D&reserved=0 
>>>>
>>>> >> >
>>>> >> > -Dave
>>>> >> >
>>>> >> > On 4/2/2022 5:05 AM, Sean A. Irvine wrote:
>>>> >> > > So far I can verify to A030077(14):
>>>> >> > >
>>>> >> > > 2022-04-02 21:46:54 1
>>>> >> > > 2022-04-02 21:46:54 1
>>>> >> > > 2022-04-02 21:46:54 1
>>>> >> > > 2022-04-02 21:46:54 3
>>>> >> > > 2022-04-02 21:46:54 5
>>>> >> > > 2022-04-02 21:46:54 17
>>>> >> > > 2022-04-02 21:46:54 28
>>>> >> > > 2022-04-02 21:46:54 105
>>>> >> > > 2022-04-02 21:46:54 161
>>>> >> > > 2022-04-02 21:46:54 670
>>>> >> > > 2022-04-02 21:46:55 1001
>>>> >> > > 2022-04-02 21:47:00 2869
>>>> >> > > 2022-04-02 21:47:58 6188
>>>> >> > > 2022-04-02 22:01:58 26565
>>>> >> > >
>>>> >> > > I adapted my existing program for A007874 to this case.  I'm 
>>>> not
>>>> sure
>>>> >> > why I
>>>> >> > > skipped over it before, but perhaps the dihedral group 
>>>> confused >> > > me.
>>>> >> The
>>>> >> > > program uses 50 digits of precision for the length >> > > 
>>>> determination. I
>>>> >> feel
>>>> >> > > like it should be possible to do this without any kind of >> 
>>>> > > precision
>>>> >> > limit,
>>>> >> > > but I don't have the time for that now. I'll leave it running
>>>> >> overnight.
>>>> >> > >
>>>> >> > > I'll also start a run for A007874 itself which also has four
>>>> >> > > additional terms with a(15) looking a little suspicious.
>>>> >> > >
>>>> >> > > Sean.
>>>> >> > >
>>>> >> > >
>>>> >> > >
>>>> >> > > On Sat, 2 Apr 2022 at 16:22, Neil Sloane <njasloane at gmail.com>
>>>> wrote:
>>>> >> > >
>>>> >> > >> To Seq Fans, The creator of an interesting sequence, A030077,
>>>> >> > >> Daniel Gittelson, submitted 12 terms in 1999, and 4 more terms
>>>> were
>>>> >> > >> added in
>>>> >> > 2007
>>>> >> > >> by a former editor. Daniel G. wrote to me today, expressing 
>>>> doubt
>>>> >> about
>>>> >> > the
>>>> >> > >> 4 additional terms.
>>>> >> > >>
>>>> >> > >> He says he interrupted his study of sequences to pursue a 
>>>> medical
>>>> >> > career,
>>>> >> > >> but now that he is retired, he can return to combinatorics.
>>>> >> > >>
>>>> >> > >> It would be nice if someone could verify the terms! (It is 
>>>> not at
>>>> >> > >> all obvious to me how to do this.)
>>>> >> > >>
>>>> >> > >> Neil Sloane
>>>> >> > >>
>>>> >> > >> --
>>>> >> > >> Seqfan Mailing list - 
>>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335528344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=xdPrlRlMV1Qypeuitcg7DKtle7i26VReYdxeYNmMXSo%3D&reserved=0
>>>> >> > >>
>>>> >> > > --
>>>> >> > > Seqfan Mailing list - 
>>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335528344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=xdPrlRlMV1Qypeuitcg7DKtle7i26VReYdxeYNmMXSo%3D&reserved=0
>>>> >> >
>>>> >> > --
>>>> >> > Seqfan Mailing list - 
>>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335684584%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ZAFqRLYFd%2BRfb88nWu3PiIO503bZNTQIFyfWRgGOeL8%3D&reserved=0
>>>> >> >
>>>> >>
>>>> >> --
>>>> >> Seqfan Mailing list - 
>>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335684584%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ZAFqRLYFd%2BRfb88nWu3PiIO503bZNTQIFyfWRgGOeL8%3D&reserved=0
>>>> >>
>>>> >
>>>> >--
>>>> >Seqfan Mailing list - 
>>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335684584%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ZAFqRLYFd%2BRfb88nWu3PiIO503bZNTQIFyfWRgGOeL8%3D&reserved=0
>>>> >
>>>> >
>>>>
>>>> -- 
>>>> Seqfan Mailing list - 
>>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335684584%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ZAFqRLYFd%2BRfb88nWu3PiIO503bZNTQIFyfWRgGOeL8%3D&reserved=0
>>>>
>>>
>>> -- 
>>> Seqfan Mailing list - 
>>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335684584%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ZAFqRLYFd%2BRfb88nWu3PiIO503bZNTQIFyfWRgGOeL8%3D&reserved=0
>>>
>>>
>>
>> -- 
>> Seqfan Mailing list - 
>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cd051b069fdd84023c97908da15f207f4%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846432335684584%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ZAFqRLYFd%2BRfb88nWu3PiIO503bZNTQIFyfWRgGOeL8%3D&reserved=0
>
> -- 
> Seqfan Mailing list - http://list.seqfan.eu/