[seqfan] wave-like patterns in a conjecture about circular differences

[Jon Wild]

Dear sequence fans,

I recently read about a conjecture published by Bryan Thwaites: starting 
from a list of N numbers, repeatedly take their N successive differences, 
including the "wrap-around" difference between last and first entry. 
Thwaites reported the conjecture (since proven) that eventually, as long 
as N is a power of 2, you'll end up with differences that are all zeroes. 
See https://www.futilitycloset.com/2018/11/29/two-puzzles-2/

For some given N, I thought I would see what would be the highest number 
of times you'd have to iterate before obtaining all zeroes, for different 
maximum entries in the starting list. So for a list of 8 numbers, for 
example, the longest chain before hitting all zeroes will have the 
following length, dependent on the highest number in the list (determined 
empirically by testing all lists):

max entry m  |   longest chain    |    starting list
-------------|--------------------|---------------------
     1        |         8          |    {1,0,0,0,0,0,0,0}
     2        |         8          |    {2,0,0,0,0,0,0,0}
     3        |        14          |    {3,0,0,0,0,0,0,1}
     4        |        15          |    {4,0,0,0,0,0,1,2}
     5        |        15          |    {5,0,0,0,0,0,3,3}
     6        |        15          |    {6,0,0,0,0,0,1,4}
     7        |        18          |    {7,0,0,3,6,1,7,0}
     8        |        21          |    {8,0,0,0,1,2,4,4}
     9        |        21          |    {9,0,0,0,1,4,1,4}
    10        |        22          |    {10,0,0,1,3,6,10,5}
    11        |        22          |    {11,0,0,0,0,1,5,4}
    12        |        22          |    {12,0,0,0,0,2,6,7}
    13        |        22          |    {13,0,0,0,0,0,7,11}
    14        |        22          |    {14,0,0,0,0,0,0,3}
    15        |        22          |    {15,0,0,0,0,1,5,6}
    16        |        22          |    {16,0,0,0,0,0,4,7}
    17        |        22          |    {17,0,0,0,0,0,2,8}
...

The middle column gives a sequence, and I'll be submitting three 
sequences to the OEIS, namely the length of the longest chain as a 
function of m, for starting lists of 4, 8, and 16 numbers.

Now, there are lots of other starting lists that produce the maximum 
length for each m--the ones shown above just happen to be the earliest 
ones my program found that remained unbeaten in length. So I was also 
curious about the overall distribution of chain lengths for each value of 
m, to see what the range of expected lengths might be, not just the 
maximum length. I programmed a sample of millions of randomised lists, I 
noted how long each list took to reach all zeroes, and here is where I 
found something that looked pretty interesting. I had my program output 
bar charts for various values of m, showing the percentage of lists that 
survived for each length of iterations before achieving all zeroes. The 
pdf file linked below applies to the case N=16, and gathers together 
graphs showing the frequency (as a percentage) of each chain-length 
required to reach all zeroes, for randomly filled lists of 16 numbers 
whose highest value m is shown at the top of each graph:

http://www.music.mcgill.ca/~wild/16numbers_diffToZero_100andUp.pdf

So the first page says that for lists of 16 numbers where the greatest 
entry is 100, almost 20% of random lists require exactly 30 iterations of 
taking differences before all zeroes are achieved, followed closely by 
lists that require 31, then 29 iterations. There are smaller peaks in the 
graph, one to the left cresting at 16 iterations, and to the right 
cresting somewhere in the mid-40s, and there's a long tail of very low 
probabilities stretching off far to the right.

If you can download and display that pdf so it shows a single page at a 
time, and if you then flip through the different charts to simulate 
animation of the results, you will see a wave-like pattern emerge as m 
varies from 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000 etc. Or 
in fact I just stitched those images together into an animated gif which 
you can view here:

https://imgur.com/a/rjzNSdr

That seems like interesting behaviour, no? As you can see the waves are 
"standing", in that the peaks and troughs remain in constant position as 
the wave washes by, gradually flattening out. Successive troughs are 
separated by 15, with minima appearing for lengths of 17, 32, 47, 62, 
77...

I left off the lowest values of m in this series of charts, because the 
initial crest they form, at a chain length of 16, overwhelms the scale of 
these charts. (It starts at 50% when m=1; you can see the tail end of that 
crest in the first of the series of charts.)

The behaviour for N=4 looks quite different:

http://www.music.mcgill.ca/~wild/4numbers_diffToZero.pdf

Here the "wave" has a single crest, doesn't go anywhere, and the 
distribution settles down and hardly changes between N=500 and 
N=5,000,000, with close to 50% (maybe tending to exactly 50%?) of all 
lists requiring only 4 iterations to reach zeroes.

The behaviour for N=8 is predictably intermediate between the previous 
two cases:

http://www.music.mcgill.ca/~wild/8numbers_DiffsToZero.pdf

Here an early series of waves collapses into an asymmetrical blob and 
doesn't change much over the last few increases in order of magnitude, 
with an ill-defined "peak" just perceptible at lengths of around 20 or 21.

Not sure what else to do with these observations other than post these 
pictures here, as I have no mathematics to share! Seems like it might 
interest sequence fans though--does anyone have any insight?

Jon Wild