5
$\begingroup$

I posted this question to Mathematics Stack Exchange but got no answers. I hope that this question is advanced enough for this forum:

In Pascal's triangle, each number is the sum of the two numbers directly above it. I experimented with a modified Pascal's triangle. First a n-tuple of natural numbers is put to the n:th row of the triangle so that the first element of the n-tuple is put to the first item in the n:th row of the triangle, second element of the tuple to the second item in the n:th row of the triangle all the way to the n:th item. Then the items of the n+1:th row are calculated as the sum of the square-free part of the left number above and square-free part of the right number above (instead of a direct sum) the item. The next rows are calculated similarly ad infinitum.

I played with the modified triangle with the computer and numerical evidence suggests that for any n-tuple, there exists a natural m such that all entries in the modified triangle are less than m. In my experimentations, the slowest part was to compute the square-free part of a number and my tests were limited by this. I computed the square free part and primality by brute force.

The largest value in the triangle may grow quite fast as the number of elements and the elements themselves in the initial tuple grow. For instance with the tuple (7) the largest value seems to be 2352, with (2,3) 36576 and with (5,3,7) 127039544.

I wonder if there is something non-trivial going on. Is there a way to prove or disprove the conjecture or to improve the numerics from brute force?

Example triangle: $$\begin{eqnarray}7\\7,7\\7,14,7\\ 7,21,21,7\\7,28,42,28,7\\7,14,49,49,14,7\\7,21,15,2,15,21,7\\7,28,36,17,17,36,28,7\end{eqnarray}$$

$\endgroup$
2
  • $\begingroup$ Try instead computing modulo 4 or modulo 9. Whenever you hit a zero, pick a small nonzero number and use it instead of zero in computing the sums below. Think of this step as dividing by 4 (or by 9). If you can go more than two rows without using a zero, there is a chance of growing coefficients. Otherwise you have something that is upper bounded by Pascal's triangle divided by some power of 4 . If you can show that power is like 4^{n/2}, there is your bound. Gerhard "it's More Complicated Than That" Paseman, 2019.03.23. $\endgroup$ Commented Mar 23, 2019 at 15:16
  • $\begingroup$ m.se posting is math.stackexchange.com/questions/3141041/… $\endgroup$ Commented Mar 24, 2019 at 8:32

1 Answer 1

2
$\begingroup$

The evidence seems much stronger for the entries to be unbounded. On the other hand, each diagonal parallel to an edge has bounded entries and hence is eventually periodic since the previous is.

If you start with $[7]$ then row $82$ is

$7, 28, 22, 2, \cdots 10620, 7640, {\Large \mathbf{2352}}, 2590, \cdots $$289800, {\Large \mathbf{629736}}, 436408, 103008, 11003 \cdots$

So it does have $2352$ in it but the largest thing in that row is much larger.

The largest entries of the remaining rows up to $100$ are

$266536, 106073, 201592, 205778, 398021, 685698, 1175313,$$ 2248918, 3564296, 4520942, {\large\mathbf {8790873}} , 6505052, 6988090,$$ 1301717, 2558155, 3815406, 3311175, 749856$


However, the band made of the first $m$ entries (also last $m$ entries) of each row is bounded.

For example it turns out that if a particular row starts with $7$ then from some point on the rows might start, as above

$7,14 \\ 7,21 \\ 7,28 \\ 7,14 \\ 7,21 \\ 7,28 \\$

I will abbreviate that pattern of second entries as $[14,21,28]$. There are only two other possible pattern for $7$, namely $[8,9]$ and $[10,17,24,13,20,12]$

This can be explained as follows: To see the possible sequence of second entries we can make a directed graph of out-degree $1$ with an edge from $c$ to the square-free part of $7+c.$ The three patterns above can be seen to be cycles in this graph. We can check that any $c$ under $17$ ends up at one of those cycles after a few steps. We can finish by showing that any $c \geq 17$ arrives in $4$ steps or less at a number less than $c.$

If we have a row starting $7,c$ then the starts of the next rows are

  • $7,d$ for $d=7+\frac{c}{t^2}$
  • $7,e$ for $e=7+\frac{d}{t^2}$
  • $7,f$ for $f=7+\frac{e}{t^2}$
  • $7,g$ for $g=7+\frac{f}{t^2}$

Here the $t^2$ in each denominator is the largest square dividing the corresponding numerator. Now perhaps $c,d,e,f=c,c+7,c+14,c+21$ but then

$c,d,e,f \bmod 4=3,2,1,0$ so one of $d,e,f,g$ is $7+\frac{c+7j}{t^2}$ for $t \geq 2$ and $j \leq 3.$ For $c \gt \frac{49}3,$ we have $7+\frac{c+21}{4} \lt c.$

So any row $7,c$ with $c>16$ is followed soon by $7,c'$ with $c' \lt c.$ Once a second entry repeats, a period is confirmed.

In general, if a row begins with $a$ which is square-free and $p$ is the smallest prime not dividing $a$ then eventually all second entries are no larger than $p^2a$ and they are periodic with a period no larger than $p^2-1.$

A quick example: For $a=15$ eventually one has in the second entries one of

  • a fixed point of $16$ or $20$
  • the period two cycle $[17,32]$
  • the period $4$ cycle $ [22, 28, 52, 37]$
  • the period $5$ cycle $[26, 41, 56, 29, 44]$

What happens in later diagonals is a similar argument. I'll give an example and a sketch.

Suppose we have first entry $7$ and second entries $[10,17,24,13,20,12].$ It turns out that after a while the first three entries of rows follow one of these patterns

$\\7, 10, 22\\7, 17, 32\\7, 24, 19\\7, 13, 25\\7, 20, 14\\7, 12, 19\\7, 10, 22\ \ \ \ $ $7, 10, 34\\7, 17, 44\\7, 24, 28\\7, 13, 13\\7, 20, 26\\7, 12, 31\\7, 10, 34\ \ \ \ $$7, 10, 14\\7, 17, 24\\7, 24, 23\\7, 13, 29\\7, 20, 42\\7, 12, 47\\7, 10, 50\\7, 17, 12\\7, 24, 20\\7, 13, 11\\7, 20, 24\\7, 12, 11\\7, 10, 14\\$

To show that the behavior is eventually periodic we show that there must be some $N$ large enough that any row starting $7,10,c$ with $c \geq N$ leads eventually to one starting $7,10,c'$ with $c' \lt c.$ This implies infinitely many rows starting $7,10,b$ with $b \lt N.$ So, eventually one appears for a second time and the periodic behavior is established.

To show that the possibilities I listed are the only ones that can occur, it suffices to not only show there is such an $N$ but to find one and then check that each start $7,10,c$ with $c \lt N$ leads to one of these periods. I will argue that $N=1000$ is large enough. In this particular case it turns out that $7,10,c$ results, 6 rows further down, in $7,10,c'$ with $c' \lt c$ with the exceptions of $1 \leq c \leq 14$ and $16,19,21,25.$

Here is how we see that there is some $N$: There is a bounded possible jump between successive third entries. Here they can never jump by more than $17.$ If with some frequency we divide by $4$ (or a larger square) then any large enough third entry is later followed by a smaller one. This is enough to keep all later third entries bounded which, in turn, means that eventually we will have two rows with the same three first entries and periodicity is established.

Here are specifics for this case: I claim that if we have a third entry $c$ then no future third entry can exceed $c+48\cdot 54$ and some future entry will be smaller than $\frac{c+54\cdot 48}{4}+5.$ But if $c \geq 936$ then $\frac{c+54\cdot 48}{4}+54 \leq c.$

If at some point we have a row starting $7,10,c$ then maybe the next rows start

$\\7, 10, c\\7, 17, c+10\\7, 24, c+27\\7, 13, c+33\\7, 20, c+46\\7, 12, c+51\\7, 10, c+54 $

The rows which start $7,10,x$ starting at x=c might perhaps have third entries $c+54j$ for $0 \leq j \leq 48.$ But these are distinct $\bmod 49$ so one of those entries would have to be a multiple of $49$ and the next such row would start $7,10,y$ for $$y \leq \frac{c+54\cdot 48}{4}+54$$

As remarked, for $c \geq 936$ we have $y \leq \frac{c+54\cdot 48}{4}+54 \leq c.$

In this specific example we note that the entries $c,c+10,c+27,c+33$ are distinct $\bmod 4.$ However that is particular to this example.

The argument given did not use anything specific to this example except that the second entries have some period (namely $6$) and the third entries have some upper bound on the possible increase every $6$ rows (namely $54$.) And, since $49$ is a square prime to $54$, we can't go through more than $48$ groups of $6$ rows without getting a division by at least $4.$

$\endgroup$
4
  • $\begingroup$ Given a rational number r with square free numerator, and h a "history of prime factors not dividing previous numerators", generate 1+(r/k^2) where k divides r and k is coprime to h, and let the new history be h times (numerator of r/k). You can generate a tree this way of potential rationals r starting with r=1, and getting rationals with nonsquarefree numerator sometimes. In this latter case, take the single step of generating 1+r/n^2 where n^2 is the largest square factor of the numerator of r, and leave the history unchanged. Gerhard "Wonders How Long Cycles Are" Paseman, 2019.03.26. $\endgroup$ Commented Mar 26, 2019 at 16:22
  • $\begingroup$ @AaronMeyerowitz I could match your calculations for the row 82 starting with [7]. This is a bit embarassing. Turned out that I wrote "square-free part" where I should have written "radical" (product of the distinct prime numbers dividing a number) in my question. Should I edit the question, post a new question or leave it as it is ? $\endgroup$
    – We Pretty
    Commented Mar 28, 2019 at 14:20
  • $\begingroup$ The radical is bigger than the square free part (or equal to it if the number itself is square free)) so that would only accelerate the growth rate. The periodicity would not change. $\endgroup$ Commented Mar 28, 2019 at 14:51
  • $\begingroup$ @AaronMeyerowitz Thank you very much for your time $\endgroup$
    – We Pretty
    Commented Mar 31, 2019 at 10:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .