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@mailman.xmission.com <math-fun-request@mailman.xmission.com> wrote:
Send math-fun mailing list submissions to math-fun@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@mailman.xmission.com
You can reach the person managing the list at math-fun-owner@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@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Signed area puzzle Message-ID: <CA+G9J-ekGr-WUuRPXUzsihYm89+excuD30RsJcU1L8v7GCG+4Q@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@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@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@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@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@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@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@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@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@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@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Signed area puzzle Message-ID: <CA+G9J-dQex92gGXfnMbWc6+52iWw79fZfYonwXJkkyZO2ovxyw@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@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Perm polys & factorial bases Message-ID: <E1ajUJR-0001lz-Sp@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@msri.org> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Perm polys & factorial bases Message-ID: <C7836F21-E9CE-4D6E-B39D-DB9F506B724A@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@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@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)