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

[Robert Gerbicz]

Exact method to identify walks with the same total length, and a proof that
for the n=p prime you won't see a collision (unless the two  walks are
permutations of each other).

On a unit circle (R=1) jumping from the k-th point to the (k+-i)-th point
has length=2*sin(i*Pi/n).

For n>2 if we're jumping i points (from k to k+-i) on the circle for v[i]
times, in the other walk w[i] times and the total length is the same then:
(we allow 0<i<n, we could restrict to i<=n/2, but indexing would be harder
later on)

sum(i=1,n-1,v[i]*sin(i*Pi/n))=sum(i=1,n-1,w[i]*sin(i*Pi/n)) and
sum(i=1,n-1,v[i])=sum(i=1,n-1,w[i])=n-1

let c[i]=v[i]-w[i] then

sum(i=1,n-1,c[i]*sin(i*Pi/n))=0 and sum(i=1,n-1,c[i])=0 is also true.

let z=cos(2*Pi/(2*n))+I*sin(2*Pi/(2*n)) primitive (2*n)-th root.

observe that sin(i*Pi/n)=(z^i+z^(n-i))/2

so we can write that: sum(i=1,n-1,c[i]*(z[i]+z^(n-i)))=0, hence
sum(i=1,n-1,(c[i]+c[n-i])*z^i)=0 is also true.

It means that z is a root of the sum(i=1,n-1,(c[i]+c[n-i])*x^i)=0 equation.

So you'll see a collision iff polcyclo(2*n,x) cyclotomic polynom divides
the f(x)=sum(i=1,n-1,(c[i]+c[n-i])*x^i) polynom.

And this is an exact method, not using floating point numbers, just
(integer) polynom divisibility.
moreover in the n=p odd prime special case for different v,w tuplets you
won't see a collision (only in the v[i]+v[p-i]=w[i]+w[p-i] for all i,
trivial case):

g(x)=polcyclo(2*p,x)=sum(i=0,p-1,(-1)^i*x^i) can't divide f(x), because g
has degree=p-1 so f should be a constant multiple of g.
f(x)=const*g(x), but then put x=1:
f(1)=const*g(1) is impossible since g(1)=1 and
f(1)=sum(i=1,p-1,(c[i]+c[p-i]))=0.

Unless const=0, but then f=0, so c[i]+c[p-i]=0 for all 0<i<p and this means
(v[i]-w[i])+(v[p-i]-w[p-i])=0 from this v[i]+v[p-i]=w[i]+w[p-i] giving that
the walks are just permutations of each other.

David Applegate <david at bcda.us> ezt írta (időpont: 2022. ápr. 2., Szo,
15:03):

> 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
>
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3838&rep=rep1&type=pdf
> ).
> 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://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010
> https://topp.openproblem.net/p33
>
> https://refubium.fu-berlin.de/bitstream/handle/fub188/18449/1993-13.pdf;jsessionid=89F489131478714C98250CFA34AFBFE7?sequence=1
>
> -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 - http://list.seqfan.eu/
> >>
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>