March 2016 - mathfun@mailman.xmission.com

Re: [math-fun] Why elliptic curve superior to RSA
by Henry Baker 26 Mar '16

26 Mar '16

The problem with fixing a curve is that with enough memory, someone can do some pretty elaborate precomputation. This is part of the problem with NIST's ECC random number generator: you couldn't trust it not to have a back door. Indeed, Juniper found to their horror that their ECC systems did indeed have such a back door, although it isn't clear who else had the backdoor key -- NSA? Chinese? Israeli's? Russians? Better to take the hit on using RSA with seriously large primes, and carefully choosing different ones each time. At 09:03 AM 3/26/2016, Warren D Smith wrote: >It is more of a pain to use elliptic curve systems since you need to find a good curve, etc, >which is not trivial. In contrast for RSA, finding suitable primes is pretty easy. >However, that only needs to be done once, then the whole world can use >just that one curve forever after. Standardize a good one.

1 0

[math-fun] Why elliptic curve superior to RSA
by Warren D Smith 26 Mar '16

26 Mar '16

Well, RSA can be broken by integer factoring, and for factoring there is a subexponential time algorithm, namely the number field sieve, which will factor N-bit-long integers in time of order about 2^O(cuberoot(N)). Consequently to get security with RSA you need very large numbers, say 1024 bits long, which makes it slow. Meanwhile for elliptic curve cryptosystems, only ways I know to break them take exponential time, 2^O(N) using N-bit long integers. You can get security using integers only say 128 bits long. (Note: I am not being careful here about my security estimates, but other people have tried to carefully estimate security and how many bits you need.) More security in less time with less memory. And the underlying reason is: that integers mod primes form a field, and integers a ring, whereas for elliptic curves, we only have a mere group. Point of that is, there is more mathematical structure usable for attacking the RSA cryptosystem than elliptic curve systems. Which is why they were able to develop subexponential attacks. It is more of a pain to use elliptic curve systems since you need to find a good curve, etc, which is not trivial. In contrast for RSA, finding suitable primes is pretty easy. However, that only needs to be done once, then the whole world can use just that one curve forever after. Standardize a good one. Both methods are breakable with a quantum computer. There are public key cryptosystems hopefully immune to quantum computers but the last time I looked they were not attractive to me in the sense they need a lot of time and memory -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Chebyshev/Dickson representation of polynomials
by Henry Baker 26 Mar '16

26 Mar '16

The really cool Chebfun computer algebra system represents polynomials in a Chebyshev basis instead of a "monomial" (power) basis: www.chebfun.org Among other things, there are "fast" algorithms for computing products of polys in a Chebyshev basis. The recent discussions of "permutation polynomials" led to finding that some of these polynomials are *Dickson* polynomials -- i.e., Chebyshev polynomials! Soooo, inspired by Chebfun, perhaps polynomials over finite fields should also be represented by Chebyshev/Dickson polynomials. Such a representation inverts the discussion, because we are now representing (at least in some cases) non-permutation polynomials in terms of permutation polynomials. Perhaps someone has already done this?

2 2

[math-fun] Perm polys & factorial bases
by Henry Baker 26 Mar '16

26 Mar '16

I'm still wondering if there are simple correspondences between factorial representations and permutation polynomials. For simplicity, let's focus only on a prime # of elements. For example, over GF(p) there are p! permutations. Is there a polynomial form in which we have exactly p choices for one of the coefficients, exactly p-1 choices for the next coefficient, exactly p-2 choices for the next coefficient, and so on? What if the p basis functions are things other than monomials x, x^2, x^3, etc. ? With function composition, we can do the following: f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth. A form such as this should be relatively easy to manufacture. So it should be possible to represent any permutation in this fully-nested "standard" form. Are there forms involving multiplication instead of composition? Are there forms involving addition instead of composition?

6 6

[math-fun] permuting via rational functions
by Warren D Smith 25 Mar '16

25 Mar '16

It seems this question by D.Asimov was studied already by L.Redei: Acta Sci Math Szeged 11 (1946) 85-92 R.Nobauer: Acta Sci Math Szeged 50 (1986) 287-298 W. Nobauer: Period. Math. Hungar. 17 (1986) 37-44. (all in German) perhaps DA will be so kind as to report what they did? This one in English apparently has something to do with it too: Leonard Carlitz: A note on permutation functions over a finite field, Duke Math. J. 29 (1962) 325-332.

1 1

[math-fun] Chebyshev/Dickson public key cryptosystem
by Warren D Smith 25 Mar '16

25 Mar '16

I hereby invent a cute (new? old?) idea. It is based on the composition identity for Chebyshev polynomials T[n](T[m](x)) = T[n*m](x) and the fact that 2*T[n](x) = (x+sqrt(x^2-1))^n + (x-sqrt(x^2-1))^n. We conclude from the latter that in a finite field with q elements, q odd, T[q^2](x) = x. Actually, maybe even T[q](x)=x in many cases, but anyhow q^2 should definitely work. More generally, 1+k*(q^2-1) will work for any integer k: T[1 + k*(q^2-1)](x) = x. So, play the usual RSA cryptosystem game, but using Chebyshev/Dickson polynomials instead of powers. Specifically, let M be a product of two large private primes M=p*q. Let the plaintext message be x mod M. The ciphertext is y=T[a](x) mod M. To decrypt it compute x=T[b](y) mod M. Here a*b=1 modulo LCM(p^2-1, q^2-1). If I know the factors p and q of M, then it is easy for me to compute the decryption key b corresponding to any given encryption key a. But there seems no easy way to do that otherwise. So, there it is. You may ask: "why should I use this instead of plain RSA?" Actually, I think RSA is a bad choice in the sense that elliptic curve systems are superior. But anyhow, I do not know. Seems like the Chebyshev /Dickson approach is somewhat costlier than RSA for same security. Still breakable with a quantum computer. It has more parameters you can twiddle (Dickson's parameter), which might be useful for enabling some application for which plain RSA is insufficient? But what? On 3/25/16, math-fun-request(a)mailman.xmission.com <math-fun-request(a)mailman.xmission.com> wrote: > Send math-fun mailing list submissions to > math-fun(a)mailman.xmission.com > > To subscribe or unsubscribe via the World Wide Web, visit > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > or, via email, send a message with subject or body 'help' to > math-fun-request(a)mailman.xmission.com > > You can reach the person managing the list at > math-fun-owner(a)mailman.xmission.com > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of math-fun digest..." > > > Today's Topics: > > 1. Re: Signed area puzzle (James Propp) > 2. Signed area puzzle (James Propp) > 3. Perm polys & factorial bases (Henry Baker) > 4. Re: Perm polys & factorial bases (Dan Asimov) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Thu, 24 Mar 2016 18:08:32 -0400 > From: James Propp <jamespropp(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Signed area puzzle > Message-ID: > <CA+G9J-ekGr-WUuRPXUzsihYm89+excuD30RsJcU1L8v7GCG+4Q(a)mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > I think I can fill the gap that Allan refers to in the last part of his > message. The key insight is that an array of numbers corresponds to a > multipath if it only if numbers in adjacent cells differ by at most 1. > (BTW, it's probably best to imagine a ring of zeros at the frontier of the > array; it follows that all the numbers in the next ring must be 1s and 0s.) > This means that we can demote cells in numerical order, from largest to > smallest (subject to the constraint that we stop demoting a cell when > it achieves its target value), without ever violating the "Lipschitz > constraint". More details upon request for anyone who wants them. > > What I still don't get is why each demotion decreases the number of > components by at most 1. Come to think of it, I'm not even sure what the > right definition of number-of-components should be in order to make such a > claim true. > > Jim > > On Thursday, March 24, 2016, Allan Wechsler <acwacw(a)gmail.com> wrote: > >> I think the proof sketch by Tom can probably be rigorized, but at this >> moment I think I see a tacit assumption that is not justified by the >> stated >> argument. It is that *any optimal single-path solution can be derived by >> "cell demotion" from the optimal multiple-path solution*. The sketch as >> currently presented ignores the philosophical possibility that there is a >> magical single-path solution that is *not* connected by cell-demotion >> with >> the nested-square configuration. I find it very hard, intuitively, to >> believe that such magical solutions exist, but I don't immediately see a >> demonstration that they don't. >> >> On Thu, Mar 24, 2016 at 2:03 PM, Tom Rokicki <rokicki(a)gmail.com >> <javascript:;>> wrote: >> >> > Okay, the proof as I see it has these components: >> > >> > 1. There's an optimal configuration without the connectedness >> > requirement that consists of k nested squares; each square >> > is a closed edge path. >> > >> > 2. There's an existing construction (due to Allan) that makes >> > slight perturbations to this (k-1 changes to link the k edge rings >> > on a 2k x 2k board). This construction also makes the edges >> > connected, with even degree on each point, so there's a >> > Hamiltonian path with strictly clockwise (or counterclockwise) >> > directions. This construction simply decreases the PSWN on >> > k-1 cells from which the edge changes can be derived. >> > >> > 3. In order to link an edge path to another, where the first lies >> > entirely inside the second, we need to change at least one >> > cell that is inside the first edge path and outside the other. >> > If there is one edge path not connected to >> > but entirely inside the another edge path, then there's a set of >> > cells with the same PSWN that separate the two edge paths. >> > >> > 4. Since there are k unconnected nested rectangles to link, we >> > need to make at least k-1 cell changes to link them. By (2) >> > we know how to do this. >> > >> > >> > On Thu, Mar 24, 2016 at 6:12 AM, James Propp <jamespropp(a)gmail.com >> <javascript:;>> wrote: >> > >> > > It's also interesting to look at my example going in the reverse >> > direction, >> > > from >> > > >> > > 101 >> > > 010 >> > > 101 >> > > >> > > to >> > > >> > > 101 >> > > 000 >> > > 101. >> > > >> > > The central square starts out with winding-number x=1, unlike its >> > > four >> > > neighbors, which start out with winding-number x-1. When we reduce >> > > the >> > > winding-number at the middle from x to x-1, we turn a 1-component >> picture >> > > into a 4-component picture. Right? (Actually, maybe Tom and Gareth >> would >> > > call the initial picture a 2-component picture, but either way, the >> > number >> > > of components goes UP, and by more than 1.) >> > > >> > > This makes it hard for me to understand the passage "Ah, but wait: >> > > this >> > is >> > > OK, because decrementing one PSWN can only unify path components when >> the >> > > PSWNs inside them become equal to the PSWN of the square we're >> changing." >> > > >> > > Jim >> > > >> > > On Thu, Mar 24, 2016 at 9:03 AM, James Propp <jamespropp(a)gmail.com >> <javascript:;>> >> > wrote: >> > > >> > > > Actually, I goofed last night: what I had in mind was a comparison >> > > > of >> > > > >> > > > 101 >> > > > 000 >> > > > 101 >> > > > >> > > > ("before") and >> > > > >> > > > 101 >> > > > 010 >> > > > 101 >> > > > >> > > > ("after"). The intuition behind my example will be clearer if I >> explain >> > > > these arrays as (grid-)multipaths. Label the nine vertices as >> > > > >> > > > ABCD >> > > > EFGH >> > > > JKLM >> > > > NOPQ >> > > > >> > > > (I left out "I" because it's so narrow, since so many of us use >> > > > non-fixed-width mail-readers). >> > > > >> > > > Start with a 4-component multipath consisting of the closed paths >> > AEFBA, >> > > > JNOKJ, LPQML, and CGHDC. Now add the four edges FK, KL, LG, and GF. >> We >> > > get >> > > > the 1-component path AEFKJNOKLPQMLGHDCGFBA, and only the winding >> number >> > > > around the center square has changed. (I hope I got it right this >> > time!) >> > > > Anyway, the multipath changes from having four components to having >> > just >> > > > one component. (Unless Tom and Gareth are using a different >> definition >> > of >> > > > components.) >> > > > >> > > > Anyway, in addition to wanting to understand better why there must >> > > > be >> > at >> > > > least k-1 grid-squares at which single-component pattern doesn't >> > achieve >> > > > maximal winding number, I'd like to know the constraints on the >> > locations >> > > > of those grid-squares. In Allan's example, the grid-squares were >> > > > all >> on >> > > the >> > > > same diagonal. Is that forced by Tom and Gareth's analysis (which >> > > > I'm >> > > still >> > > > trying to understand)? >> > > > >> > > > Jim >> > > > >> > > > On Thu, Mar 24, 2016 at 7:03 AM, James Propp <jamespropp(a)gmail.com >> <javascript:;>> >> > > wrote: >> > > > >> > > >> I expect that Gareth and Tom will find my remarks about >> > > >> >> > > >> 010 >> > > >> 111 >> > > >> 010 >> > > >> >> > > >> obtuse and irrelevant, since local configurations like that won't >> > occur >> > > >> as one successively mutates the array (starting from the maximal >> array >> > > and >> > > >> lowering k-1 entries one at a time). But how do we KNOW they >> > > >> won't? >> > > Clearly >> > > >> Tom and Gareth have some additional intuitions about what's going >> > > >> on >> > > here >> > > >> that aren't captured by the analyses they've offered. >> > > >> >> > > >> Jim >> > > >> >> > > >> >> > > >> On Wednesday, March 23, 2016, James Propp <jamespropp(a)gmail.com >> <javascript:;>> >> > wrote: >> > > >> >> > > >>> Thanks for taking the time to clarify, Gareth. >> > > >>> >> > > >>> 4. Whatever that reduction is, we can imagine doing it >> > > >>>> one square (and one unit of winding for that square) >> > > >>>> at a time. >> > > >>> >> > > >>> >> > > >>> This is not obvious to me, but I can prove it. (You have to >> decrement >> > > >>> the larger numbers first.) >> > > >>> >> > > >>> >> > > >>>> When we reduce one PSWN by 1, the number >> > > >>>> of path components cannot reduce by more than one -- >> > > >>>> for we cannot have components of more than two >> > > >>>> disconnected paths adjacent to a single square. >> > > >>> >> > > >>> >> > > >>> This lemma (if I'm understanding it correctly) cannot hold in >> > > >>> full >> > > >>> generality. Consider the PSWN array >> > > >>> >> > > >>> 010 >> > > >>> 101 >> > > >>> 010 >> > > >>> >> > > >>> (four separate loops) and the PSWN array >> > > >>> >> > > >>> 010 >> > > >>> 111 >> > > >>> 010 >> > > >>> >> > > >>> (a single loop); when we turn the former into the latter, a >> > > >>> single >> > PSWN >> > > >>> changes by 1, but the number of components changes by 3. >> > > >>> >> > > >>> I'll mention Allan Wechsler here, for no reason other than the >> > > >>> fact >> > > that >> > > >>> I seem to keep misspelling his first name and could use some >> practice >> > > >>> spelling it right. Allan, Allan, Allan. There! Let's see if that >> > > helps. :-) >> > > >>> >> > > >>> Jim >> > > >>> >> > > >> >> > > > >> > > _______________________________________________ >> > > math-fun mailing list >> > > math-fun(a)mailman.xmission.com <javascript:;> >> > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > > >> > >> > >> > >> > -- >> > -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link >> suppressed; >> > ask me why] -- >> > _______________________________________________ >> > math-fun mailing list >> > math-fun(a)mailman.xmission.com <javascript:;> >> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com <javascript:;> >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > > > ------------------------------ > > Message: 2 > Date: Thu, 24 Mar 2016 22:33:13 -0400 > From: James Propp <jamespropp(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: [math-fun] Signed area puzzle > Message-ID: > <CA+G9J-dQex92gGXfnMbWc6+52iWw79fZfYonwXJkkyZO2ovxyw(a)mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > Here's an almost complete proof, using ingredients from Tom's proof (but > discarding #4). First argue that there must be a way to turn the initial > "nested squares" multipath configuration into a maximal single-path > configuration via successive demotions (see my previous email). Then, claim > that at least one cell in each of the k-1 outermost rings must be demoted > in the process. For, if not, then we'd get a non-simply-connected band of > cells of constant winding-number at the end of the process, which would > disconnect the multipath into two parts (one "outer" and one "inner"). > > The only gap I see here is, why couldn't the outer part or the inner part > of the maximal single-path configuration be empty? The answer must be, This > woud contradict maximality! I think I see a way to fill the gap (two cases: > one for the outer part and one for the inner part). The first I'm 90% sure > of; the second I'm less sure of. My approach is kind of fiddly. Can anyone > find a more conceptual way of wrapping up the proof? > > Jim > > > ------------------------------ > > Message: 3 > Date: Fri, 25 Mar 2016 09:10:09 -0700 > From: Henry Baker <hbaker1(a)pipeline.com> > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] Perm polys & factorial bases > Message-ID: <E1ajUJR-0001lz-Sp(a)elasmtp-scoter.atl.sa.earthlink.net> > Content-Type: text/plain; charset="us-ascii" > > I'm still wondering if there are simple correspondences between factorial > representations and permutation polynomials. > > For simplicity, let's focus only on a prime # of elements. > > For example, over GF(p) there are p! permutations. > > Is there a polynomial form in which we have exactly p choices for one of the > coefficients, exactly p-1 choices for the next coefficient, exactly p-2 > choices for the next coefficient, and so on? > > What if the p basis functions are things other than monomials x, x^2, x^3, > etc. ? > > With function composition, we can do the following: > > f(g(h(...(q(x))...))) can be a representation of one of these p! > permutations if > > f(x) chooses one of p elements; > g(x) chooses one of p-1 elements; > h(x) chooses one of p-2 elements, > and so forth. > > A form such as this should be relatively easy to manufacture. > > So it should be possible to represent any permutation in this fully-nested > "standard" form. > > Are there forms involving multiplication instead of composition? > > Are there forms involving addition instead of composition? > > > > > ------------------------------ > > Message: 4 > Date: Fri, 25 Mar 2016 09:16:59 -0700 > From: Dan Asimov <asimov(a)msri.org> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Perm polys & factorial bases > Message-ID: <C7836F21-E9CE-4D6E-B39D-DB9F506B724A(a)msri.org> > Content-Type: text/plain; charset=utf-8 > > I'd expect that if there is such a representation, the innermost > function would be the one choosing one of p elements, the next > one would know from f(x) which element *not* to choose, and would > pick one of the p-1 remaining elements, etc. > > ?Dan > > >> On Mar 25, 2016, at 9:10 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> >> With function composition, we can do the following: >> >> f(g(h(...(q(x))...))) can be a representation of one of these p! >> permutations if >> >> f(x) chooses one of p elements; >> g(x) chooses one of p-1 elements; >> h(x) chooses one of p-2 elements, >> and so forth. > > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > ------------------------------ > > End of math-fun Digest, Vol 157, Issue 76 > ***************************************** > -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 3

[math-fun] Chebyshev polynomials, and powers; permutation polynomials
by Warren D Smith 25 Mar '16

25 Mar '16

Powers X^n are naturally associated with circles in the complex plane (contours on which |X^n| is constant). Chebyshev polynomials, are naturally associated with the ellipses with foci at +1 and -1. Chebyshev polynomials actually are powers -- in the sense that define the 2x2 matrix [2X, 1] [-1, 0] call it M, and then ( Chebyshev[n](X), Chebyshev[n-1](X) ) = V M^n where V is the row vector (1,x). [This is just the recurrence relation, rewritten.] This fact allows one to view cheb series as power series, find continued fractions (of matrices) that are good approximants over the real interval [-1,1] in the Chebyshev sense, etc. (Which I discovered about 30 years ago...) Cheb series as power series in a different way: use the eigendecomposition of that matrix to see 2*Chebyshev[n](X) = (X-sqrt(X^2-1))^n + (X+sqrt(X^2-1))^n the ellipses I was speaking of are |Z+sqrt(Z^2-1)|=const in the complex Z-plane, halfplane Re(Z)>0 anyhow. Try typing Modulus[ x+I*y+Sqrt[(x+I*y)^2-1] ] contour plot x=0..10, y=-10..10 into http://www.wolframalpha.com . So perhaps these facts give you some insight about why/how/when Chebyshev polynomials, as well as powers X^n, can be permutation polynomials if we work within finite fields. The fact the nonzeros in finite fields form a cyclic multiplicative group explains why X^n is a perm-poly if GCD(n, q-1)=1 where q=cardinality of field. It just, with respect to the cycle of powers of the generator, multiplies the discrete log by n modulo q-1. In the complex plane, R^(1-n)*Z^n as a map, maps the circle |Z|=R to itself but wound round n times not once. I claim Chebyshev[n](Z) as a map, must do the same thing about those ellipses, it just winds them n times, if scaled right. Any finite field either contains I=sqrt(-1) or not -- for example GF(5) has 2^2=-1, but GF(3) has no I. If there is no I, we can consider those "ellipses" in the "complex plane" as subsets of 2-tuples of finite field elements. Also, one can regard them just as elements of the extension field got by extending our field by adjoining I. If there is I, then the finite field "already is the complex plane" without need to take 2-tuples. Anyhow, presumably the reason Chebyshev[n] can be a perm-poly is that it walks finite field elements, or extension field elements, round ellipses. Provided all the ellipses have cardinalities coprime to n, you get a permuting effect. Now, see https://en.wikipedia.org/wiki/Dickson_polynomial#Permutation_polynomials_an… where it appears that Chebyshev polynomials and linear polynomials (and view powers as a degenerate case of chebyshev) are essentially the only useful thing there is, in the land of perm-polys. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1

[math-fun] Signed area puzzle
by James Propp 25 Mar '16

25 Mar '16

Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares. What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges? I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares). Jim Propp

5 24

[math-fun] Simpler and Faster ways to compute Sylvester's "Number Wall"
by Warren D Smith 24 Mar '16

24 Mar '16

Simpler and Faster ways to compute the "Number Wall" ==========Warren D. Smith=====March 2016============ The idea of the number wall was invented by James J. Sylvester (1814-1897). For an introduction to using it (and the "difference table") to analyse sequences, see chapter 3 of "The book of numbers" by J.H.Conway & R.K.Guy (Springer 1996), except, according to Lunnon, their discussion is marred by several errors in its details. (Lunnon doesn't actually say what those errors were, which was not very helpful.) The top three rows of the number wall are all-0, all-1, and your integer sequence S. To determine subsequent rows, the slow but safe method is this: The entry H hops vertically below sequence entry S[A] is the determinant of the KxK Toeplitz matrix whose leftmost column and top row are (if we walk up the leftmost column then rightward along the top row) S[A-K], S[A-K+1], ... S[A-1], S[A], S[A+1], ..., S[A+K-1], S[K]. This makes it obvious all entries of the number wall are integers (if the sequence was integers) and indeed if the seqeunce was elements from any commutative ring, then so are all entries of the number wall. A much faster and simpler, but not entirely safe, way to fill in the subsequent rows of the number wall is to use the "holy cross law" that any 5 numbers adjacent in a "holy cross" configuration in the number wall: . N . W X E are related by X*X = N*S + E*W. . S . The reason this is "not entirely safe" is because, e.g, trying to determine S via S=(X*X-E*W)/N might give you 0/0. (Also, if we are operating in a ring that is not a field, then division by a "zero divisor" can yield non-unique answers. It also is possible in such rings for division problems to have no solutions, but the division problems that arise inside number walls always do have solutions so that is not an issue.) That problem happens if and only if N=0 while W,X,E are in geometric progression: W*E = X*X. The best try at a rigorous and correct development seems to be W.F.Lunnon: The Number-Wall Algorithm: an LFSR Cookbook, Journal of Integer Sequences 4 (2001) Article 01.1.1 https://cs.uwaterloo.ca/journals/JIS/VOL4/LUNNON/numbwall10.pdf But in Lunnon's crux "algorithm description" page 16 his formula in step iii was wrong and presumably should have ended with G_k/C_k not C_k/M_k. Lunnon's main theorems (3.8, 4.1, 4.2, 4.3 pp.9-11) state that zero-entries in a number wall can only arise in the form of gXg square "windows in the wall" (consisting entirely of 0s) surrounded by an "inner frame" of 4(g+1) nonzero entries, where the g+2 entries forming each side (including their corners) of this inner frame, must be in geometric progression, and the 4 growth ratios for the 4 geometric progressions (regarding all 4 are progressing clockwise) must have product = (-1)^g. [Obviously if P is the product, then P^(g+1) = 1 since return to starting point after g+1 hops in each direction. That forces P to equal +1 except that if g is odd, then -1 also could be possible. And in fact, this -1 does happen.] ##aA#### #000000# #000000b Picture of gXg zero-window with inner frame #000000B showing 4 entires A,B,C,D (one per side) of the D000000# inner frame (arbitrarily located) and their adjacent d000000# predecessors a,b,c,d in clockwise order. #000000# (Here "#" means "irrelevant nonzero entry".) ###Cc### In other words, ABCD = (-1)^g abcd if A,B,C,D are any 4 entries on the inner frame (one per side) with a,b,c,d the immediately preceding entries in clockwise order. (Or anticlockwise; both directions work, so long as we are consistent.) This allows us to work out the entire inner frame from the 6 entries at and adjacent to the top two corners; indeed we need only three among the four top-row members within those six. Therefore, pick two antipodal corners of the inner frame, labeled * in the diagram below. if we have 4 entries on the inner frame, 1 per side, call them A,B,C,D such that A & D are distance k from one *-corner while B & C both are at the same distance k from the other (or A&B and C&D if we choose to star the complementary set of corners), *##A#### #000000# Picture of gXg zero-window, with inner frame. #000000# Here "#" means "irrelevant nonzero entry", D000000# and "*" means the same but the two *'s must be #000000B antipodal corners. A&D lie at same distance k #000000# from *, as do B&C from their *, where 1<=k<=g. #000000# ####C##* then A*C = (-1)^(g*k) * B*D, which is a polynomial relation of only degree=2 and enables deduction of any inner frame entry given that the other 3 sides of the inner frame are known. (Smaller degrees are better since they allow carrying fewer digits in arithmetic.) This inner frame is surrounded by an "outer frame," consisting of 4(g+2) entries. These obey ....E..... .*#aA####. .#000000#. Picture of gXg zero-window, with inner & outer frames, .d000000#. where "0" means "zero entry," HD000000#. "#" means "irrelevant nonzero entry" of inner frame, .#000000BF "*" means same as # except these must be two antipodal corners, .#000000b. and "." means "irrelevant entry" of outer frame. .#000000#. Note A,B,C,D,a,b,c,d all are nonzero. .####Cc#*. A&D lie at same distance k from *, as do B&C from their *, .....G.... where 1<=k<=g. The 12 entries labeled with letters obey (-1)^(k+g) * (A*H*c*B - C*F*a*D) = B*G*d*A - D*E*b*C. This is a new identity of polynomial degree=4 and enables deduction of any outer frame entry given that the other 3 sides of the outer frame are known. Is there any identity of degree=3? I conducted a fairly exhaustive computer search and failed to find any for the task of relating these 8 entries: ..AB.. ..CD.. EF00GH for a 2x2 window. JK00LM ..NP.. ..QR.. In other words, I suspect my degree-4 identity is best possible in the sense of having least possible degree and enabling "walking through windows," even for 2x2 windows. But in the special case of an isolated zero (1x1 "zero window") an identity of degree=3 does suffice: ..n.. ..N.. Conway & Guy bottom of p.87 claim s*N*N + n*S*S = w*E*E + e*W*W wW0Ee agreeing with Lunnon EQ 5.2 p.16. ..S.. ..s.. It now is possible to fill in the entries of the number wall row by row by an algorithm whose runtime is linear in the number of entries it computes, and which uses storage equivalent to the latest 6 rows of the wall, plus the row currently being computed as a 7th -- provided that 1. denote the 5 rows stored as V, W, X, Y and the new one (being computed) is Z, in order going down. 2. If X contains zero-entries, then assume there are special symbols available meaning "zero whose vertical location is j," where the top row of a gXg zero-window has j=1 and the bottom row has j=g, and use them. 3. If W contains zero-entries, then cheat by agreeing each entry of W that would have been 0, will contain the first nonzero entry of the number wall you'd reach by walking vertically upward from that 0. 4. And similarly cheat for V; it contains the entry immediately above the corresponding entry for W. 5. Finally up to two more rows worth of storage need to be added, which store the two vertical edges of the outer frame of each window. I point this out since for some reason Lunnon (p.23) claimed runtime and storage both a factor N larger than my claims (N is the length of a row of the number wall), except if doing arithmetic over the binary field GF(2) where he claimed to equal my bounds (but claimed going to higher fields like GF(5) would probably be "infeasible"). That all was pretty silly. With the aid of the number wall, it is easy to recognize sequences that obey linear recurrences, e.g. the powers of 2 or Fibonacci numbers. In all these cases (and some others) some pattern can be recognized inside the number wall, then used in combination with the holy-cross-relation to fill in all other entries, thereby "predicting" the sequence forever. Numerical example containing 1x1, 1x1, and 3x3 windows (latter with *'s at corners of inner frame): 0:1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1:9 8 7 5 4 1* 1 1 1 1 2 5 9 12 16 18 21 2: 1 9 -3 11 -3 0 0 0 -1 -1 7 21 0 40 -12 3: 12 -18 28 9 0 0 0 1 4 14 49 -70 100 4: 4 86 -27 0 0 0 -1 -2 0 161 7 5: 268 81 -27 9 -3 1* 1 23 529 6: -511 -76 -109 -16 -4 11 -151 7: 1849 1185 60 192 -483 8: -11865 13995 -16461 9: 9171

1 0

[math-fun] gosper.org/matrixtower.pdf
by Bill Gosper 24 Mar '16

24 Mar '16

In response to a private request, the order of evaluation of the first eight term-matrices of a Ramanujan 1/π series. The objective is to always multiply integers of comparable size. It naturally collapses to one matrix every power-of-2 terms, but is cheap to forcibly collapse occasionally, and always remains resumable, even as continued fraction terms or (feh) decimal digits are extracted by matrix multiplication on the left. (Which must imitate the fractal, "ruler function" chunking on the right to keep the integer multiplies balanced, and thus fully exploit fast arithmetic.) --rwg

1 0