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

[Brendan McKay]

It isn't about rational combinations of square roots of integers, and 
square roots don't even need to be involved.  The problem is to test a 
sum for equality to 0 where each term is an integer times sin(k pi / n) 
for integer k.  Robert Gerbicz gave a correct analysis and deterministic 
algorithm before, and I noted that Maple can do it very quickly in all 
cases I tried (thousands).

Brendan.

On 4/4/2022 5:16 am, 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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ymoaz5ksAtXDcsAjB8pXlhFOSpSge9fn4FrgXFc6v1k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=raw4WBD0l6AdQ4gEcewC3EG88yu7f3NuBpg1QLi0p7k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=wcqzn%2FljVmh4yr%2BlUttuc1M6qhfS6rJYJNSFqKwvc5Q%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=lo6Nr9tGLfGN0us7ui1VNf8ri6XhZN%2Bj%2BhDpIw1n%2B3k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=rsa9Pj%2FnqareMvatGT9m5jOb5aH0KJDmaZMh5TB0n%2BQ%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=s%2BWnjrq9%2BoAW3izYxkgoPK3tzpKTYlywEwQmHqW6V3k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=s%2BWnjrq9%2BoAW3izYxkgoPK3tzpKTYlywEwQmHqW6V3k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=s%2BWnjrq9%2BoAW3izYxkgoPK3tzpKTYlywEwQmHqW6V3k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=s%2BWnjrq9%2BoAW3izYxkgoPK3tzpKTYlywEwQmHqW6V3k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=s%2BWnjrq9%2BoAW3izYxkgoPK3tzpKTYlywEwQmHqW6V3k%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%7C4dd0dedbaacc44b1f60c08da15a683a9%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637846316996089138%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=s%2BWnjrq9%2BoAW3izYxkgoPK3tzpKTYlywEwQmHqW6V3k%3D&reserved=0