July 2017 - mathfun@mailman.xmission.com

Re: [math-fun] Matrices to represent extension field elements
by hbaker1 25 Jul '17

25 Jul '17

Yes, of course p^j, p^k, p^(jk). Ok, so in the case where p=2, jk=32, j could be 2,4,8,16 with k 16,8,4,2 respectively ? The matrix representation should be a *block matrix* representation, with an "outer" representation of 2x2, 4x4, 8x8, 16x16, and an "inner" representation of 16x16, 8x8, 4x4, 2x2, respectively. I assume that it is possible to do this incrementally, with each step being a factor of 2 -- i.e., a 2x2 array of smaller blocks? So we automatically get a Strassen-like recursive matrix multiplication algorithm for these block matrices ? -----Original Message----- >From: rcs(a)xmission.com >Sent: Jul 24, 2017 10:53 PM >To: math-fun(a)mailman.xmission.com >Cc: rcs(a)xmission.com >Subject: Re: [math-fun] Matrices to represent extension field elements > >Addressing only the third-to-last paragraph, about extensions & towers: >If j and k are relatively prime positive numbers, you can develop the >fields GF[p^j], GF[p^k], and GF[p^(jk)]. The last contains the first two >as subfields. If you select irreducible polynomials (mod p) of degrees >j and k, you can adjoin roots of both polynomials to GF[p] and get the >product degree field GF[p^(jk)]. It works, I've written the code, it runs. > >If j divides k, then GF[p^j] is embeddable as a subfield of GF[p^k]; >if you've selected a representation of GF[p^k], there's a unique subset >that makes up GF[p^j]. The embedding is unique as to the set of elements, >but not wrt the actual mapping, because of automorphisms of GF[p^j]. > >If you choose an N, and consider its divisibility box, with 1 at the >lower left front corner, and N at the opposite corner, each node J of the box >has a field GF[p^J], and the subfields have the same relationship as >the box nodes. > >Rich > >-------- >Quoting hbaker1 <hbaker1(a)pipeline.com>: >> A recent post mentioned that (square) matrices were a kind of >> "universal" representation for fields, in that a matrix A whose >> characteristic polynomial is p[x] can represent a root of this >> polynomial in the extension field. >> >> The problem is that such a matrix doesn't represent a *single* root of >> p[x], but simultaneously represents *all* of the roots of p[x]. >> (Hint: diagonalize the matrix so that the main diagonal consists of >> the eigenvalues, i.e., all the roots of p[x].) >> >> Suppose we have the simplest situation: a symmetric matrix with all >> distinct real roots. Since the matrix itself represents *all* of >> these roots simultaneously, it can't participate, e.g., in ordering >> comparisons with other numbers which may lie in the middle of this set >> of roots. >> >> So there needs to be some way to distinguish exactly which root we're >> talking about when given the matrix A, before we can realistically >> utilize this matrix as a representation of one of the real roots of >> the polynomial. >> >> --- >> >> In the usual case of real matrices with complex eigenvalues, the >> coefficients of the polynomial, the entries of the matrix, and the >> roots themselves are usually more-or-less continuous functions of one >> another. So if we vary a polynomial coefficient by a little, one or >> more of the roots will vary in a more-or-less predictable way. >> >> If we're going to extend finite fields in a p-adic way, then >> presumably there will be an analogous "continuity" between the >> polynomial coefficients and the roots. >> >> It is my understanding that all of the fields GF(p^k) with a given >> prime p and a given positive power k are isomorphic to one another. >> So does this mean that instead of extending by p^k, one could instead >> extend first by p^i, and subsequently by p^j, such that i+j=k ? >> >> Perhaps one could build (always?) some sort of "tower" of extensions >> whereby each field is embedded in the next ? >> >> Under these conditions, could the polynomial coefficients be "close" >> to those of the extensions, and the polynomial roots be "close" to >> those of the extension, where "close" is measured in some p-adic way?

1 0

[math-fun] Matrices to represent extension field elements
by hbaker1 25 Jul '17

25 Jul '17

A recent post mentioned that (square) matrices were a kind of "universal" representation for fields, in that a matrix A whose characteristic polynomial is p[x] can represent a root of this polynomial in the extension field. The problem is that such a matrix doesn't represent a *single* root of p[x], but simultaneously represents *all* of the roots of p[x]. (Hint: diagonalize the matrix so that the main diagonal consists of the eigenvalues, i.e., all the roots of p[x].) Suppose we have the simplest situation: a symmetric matrix with all distinct real roots. Since the matrix itself represents *all* of these roots simultaneously, it can't participate, e.g., in ordering comparisons with other numbers which may lie in the middle of this set of roots. So there needs to be some way to distinguish exactly which root we're talking about when given the matrix A, before we can realistically utilize this matrix as a representation of one of the real roots of the polynomial. --- In the usual case of real matrices with complex eigenvalues, the coefficients of the polynomial, the entries of the matrix, and the roots themselves are usually more-or-less continuous functions of one another. So if we vary a polynomial coefficient by a little, one or more of the roots will vary in a more-or-less predictable way. If we're going to extend finite fields in a p-adic way, then presumably there will be an analogous "continuity" between the polynomial coefficients and the roots. It is my understanding that all of the fields GF(p^k) with a given prime p and a given positive power k are isomorphic to one another. So does this mean that instead of extending by p^k, one could instead extend first by p^i, and subsequently by p^j, such that i+j=k ? Perhaps one could build (always?) some sort of "tower" of extensions whereby each field is embedded in the next ? Under these conditions, could the polynomial coefficients be "close" to those of the extensions, and the polynomial roots be "close" to those of the extension, where "close" is measured in some p-adic way?

2 1

Re: [math-fun] Stick to your guns.
by Dan Asimov 24 Jul '17

24 Jul '17

P.S. ----- The equation is in the world of meromorphic functions. ----- Well, that was the intention, anyway. But I'm out of my depth in the world of holomorphic functions of two variables >Sorry, I was using a quaint notation common in complex variables where f(z,w) denotes the function f itself (and not in this case the value of f at the point (z,w)). The equation is in the world of meromorphic functions. >—Dan >>From: Fred Lunnon <fred.lunnon(a)gmail.com> f(z,w) = 1 / beta(w+1, z-w+1) (and by symmetry = 1 / beta(z-w+1, w+1) ) unless, of course, the denominator happens to vanish ... WFL On 7/24/17, Dan Asimov <dasimov(a)earthlink.net> wrote: Needless to say: If f(z,w) is defined as f(z,w) = gamma(z+1) / (gamma(w+1) * gamma(z-w+1)) then it's a ratio of meromorphic functions, therefore meromorphic. But of course since beta(z,w) = gamma(z) gamma(w) / (gamma(z+w) then we have f(z,w) = 1 / beta(w+1, z-w+1) (and by symmetry = 1 / beta(z-w+1, w+1) ) —Dan ----- Why stop at two? There are a denumerable number of singularities of >>> Gamma(n+1) / Gamma(k+1) Gamma(n-k+1) at negative integer n , and >>> once you decide to start tinkering with approaching them from multiple >>> randomly selected directions, a whole continuum of choices opens >>> before you --- though admittedly not all of them yield integer results. >>> >>> [ And bear in mind, incidentally, that you will have royally screwed up >>> your symbolic theorem prover --- see examples from Mathematica and >>> Maple in my note. ] >>> >>> WFL >>> >>> On 7/23/17, James Propp <jamespropp(a)gmail.com> wrote: >>>> Maybe n-choose-k should actually be two-valued (like sqrt(z)), with a >>>> branch-point at n=k=0? >>> ----- >>> >>> _______________________________________________ >>> math-fun mailing list >>> math-fun(a)mailman.xmission.com >>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>> >> >>_______________________________________________ >>math-fun mailing list >>math-fun(a)mailman.xmission.com >>https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

Re: [math-fun] Stick to your guns.
by Dan Asimov 24 Jul '17

24 Jul '17

Sorry, I was using a quaint notation common in complex variables where f(z,w) denotes the function f itself (and not in this case the value of f at the point (z,w)). The equation is in the world of meromorphic functions. —Dan -----Original Message----- >From: Fred Lunnon <fred.lunnon(a)gmail.com> >> f(z,w) = 1 / beta(w+1, z-w+1) >> (and by symmetry >> = 1 / beta(z-w+1, w+1) ) > >unless, of course, the denominator happens to vanish ... WFL > >On 7/24/17, Dan Asimov <dasimov(a)earthlink.net> wrote: >> Needless to say: If f(z,w) is defined as >> >> f(z,w) = gamma(z+1) / (gamma(w+1) * gamma(z-w+1)) >> >> then it's a ratio of meromorphic functions, therefore meromorphic. >> >> >> But of course since >> >> beta(z,w) = gamma(z) gamma(w) / (gamma(z+w) >> >> then we have >> >> f(z,w) = 1 / beta(w+1, z-w+1) >> >> (and by symmetry >> >> = 1 / beta(z-w+1, w+1) >> ) >> >> —Dan >> >> ----- >> Why stop at two? There are a denumerable number of singularities of >> Gamma(n+1) / Gamma(k+1) Gamma(n-k+1) at negative integer n , and >> once you decide to start tinkering with approaching them from multiple >> randomly selected directions, a whole continuum of choices opens >> before you --- though admittedly not all of them yield integer results. >> >> [ And bear in mind, incidentally, that you will have royally screwed up >> your symbolic theorem prover --- see examples from Mathematica and >> Maple in my note. ] >> >> WFL >> >> On 7/23/17, James Propp <jamespropp(a)gmail.com> wrote: >>> Maybe n-choose-k should actually be two-valued (like sqrt(z)), with a >>> branch-point at n=k=0? >> ----- >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] Stick to your guns.
by Dan Asimov 24 Jul '17

24 Jul '17

Needless to say: If f(z,w) is defined as f(z,w) = gamma(z+1) / (gamma(w+1) * gamma(z-w+1)) then it's a ratio of meromorphic functions, therefore meromorphic. But of course since beta(z,w) = gamma(z) gamma(w) / (gamma(z+w) then we have f(z,w) = 1 / beta(w+1, z-w+1) (and by symmetry = 1 / beta(z-w+1, w+1) ) —Dan ----- Why stop at two? There are a denumerable number of singularities of Gamma(n+1) / Gamma(k+1) Gamma(n-k+1) at negative integer n , and once you decide to start tinkering with approaching them from multiple randomly selected directions, a whole continuum of choices opens before you --- though admittedly not all of them yield integer results. [ And bear in mind, incidentally, that you will have royally screwed up your symbolic theorem prover --- see examples from Mathematica and Maple in my note. ] WFL On 7/23/17, James Propp <jamespropp(a)gmail.com> wrote: > Maybe n-choose-k should actually be two-valued (like sqrt(z)), with a > branch-point at n=k=0? -----

2 1

[math-fun] Stick to your guns.
by Bill Gosper 24 Jul '17

24 Jul '17

https://en.wikipedia.org/wiki/Vanadium (at least when I browse with Chrome!) says the poor guy who discovered vanadium withdrew his claim after other chemists convinced him it was just another form of chromium. I'm guessing that a similar lapse of conviction ruined Mathematica's Binomial function: Some moron complained about the asymmetry so long after it was implemented that WRI forgot why it's asymmetrical, and accommodated the moron. I had and forgot other examples, but here's one I remember: Petr Beckmann's https://en.wikipedia.org/wiki/A_History_of_Pi originally contained Euler's 2 1 Pi Product[------, p ∈ {2, 3, 5, 7, …}] == --- 1 6 1 - -- 2 p But some doofus with a minicomputer complained that p ∈ {2, 3, 5, 7, 9, 11, …} didn't work! So Beckmann tried the same thing, and removed the formula from the next edition! --rwg I wonder why Mma disallows fancier iterators like p ∈ Primes and n≥1.

7 9

[math-fun] Stick to your guns.
by Bill Gosper 23 Jul '17

23 Jul '17

Mathematica 7.0.1: As a bivariate function, Binomial is not continuous in both variables at negative integers: In[1]:= Binomial[-3, -5] Out[1]= 0 In[2]:= Binomial[-3.0000001, -5.0000001] Out[2]= 6.00000035000001 Mathematica 11.1: The value of Binomial at negative integers is determined via Binomial[n,m]==Binomial[n,n-m]: In[2]:= Binomial[-3, -5] Out[2]= 6 GKP: The restriction that n and k be integers in identity (5.4) is obvious, since each lower index must be an integer. But why can't n be negative? Suppose, for example, that n = −1. Is −1 ? −1 ( ) = ( ) k −1−k a valid equation? No. For instance, when k = 0 we get 1 on the left and 0 on the right. In fact, for any integer k ≥ 0 the left side is −1 (−1)(−2) . . . (−k) k ( ) = ------------------- = (−1) k k! which is either 1 or −1; but the right side is 0, because the lower index is negative. And for negative k the left side is 0 but the right side is −1 −1−k ( ) = (−1) , −1−k which is either 1 or −1. So the equation −1 −1 ( ) = ( ) is always false! k −1−k The symmetry identity fails for all other negative integers n, too. But unfortunately it's all too easy to forget this restriction, since the expression in the upper index is sometimes negative only for obscure (but legal) values [ I just hope I don't fall into this trap during the midterm.] of its variables. Everyone who's manipulated binomial coefficients much has fallen into this trap at least three times. ---end GKP --- As I hope Fred's opus makes clear, this asymmetry is not a special case kludge. Remarkably, the real-valued surface Binomial[y,x] is symmetrical, but the discretized surface Binomial[n,k] = Limit[Limit[Binomial[y,x],x->k],y->n] is not! In order to maintain their symmetry fiction, WRI broke the addition formula GKP(5.8) Out[5]= Binomial[r, k] == Binomial[-1 + r, -1 + k] + Binomial[-1 + r, k] In[6]:= % /. r -> 0 /. k -> 0 Out[6]= False But they forgot to break QBinomial! In[9]:= QBinomial[-3, -5, q] Out[9]= 0 --rwg On 2017-07-22 22:00, Henry Baker wrote: > Dropbox is a pain, unless you add "?dl=1" to the end, as in: > > https://www.dropbox.com/s/9vvl6l6ym1zkret/binomial.pdf?dl=1 > > The "?" indicates that you're passing parameters, and the "dl=1" > says -- in essence -- "download equals 1 -- i.e., *yes*". > > It took me quite a while to figure this out about dropbox. > > At 06:16 PM 7/22/2017, Fred Lunnon wrote: >> @#$%^&?! ... DropBox is getting steadily less user-friendly --- >>why give me a link and immediately disable the infernal thing? >>Anyway, I have copied the file, deleted it and re-up-loaded it: >>try instead >> >> https://www.dropbox.com/s/9vvl6l6ym1zkret/binomial.pdf >> >>WFL >> >>On 7/23/17, Neil Sloane <njasloane(a)gmail.com> wrote: >>> Fred, >>> when I tried to look at your discussion, >>> https://www.dropbox.com/s/anykne0pd55ehjg/binomial.pdf >>> I got a rude "go away" message >>> >>> Best regards >>> Neil >>> >>> Neil J. A. Sloane, President, OEIS Foundation. >>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. >>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. >>> Phone: 732 828 6098; home page: http://NeilSloane.com >>> Email: njasloane(a)gmail.com >>> >>> On Sat, Jul 22, 2017 at 7:20 PM, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: >>> >>>> See the note I wrote up following a discussion on this list circa 2014 >>>> --- >>>> https://www.dropbox.com/s/anykne0pd55ehjg/binomial.pdf >>>> >>>> [ I did contemplate trying to get this published in the Math. Intelligencer, >>>> but retreated in the face of an editor's mysterious antipathy to computer- >>>> generated illustrations. ] >>>> >>>> WFL >>>> >>>> On 7/22/17, Gareth McCaughan <gareth.mccaughan(a)pobox.com> wrote: >>>> >> I'm guessing that a similar lapse of conviction ruined Mathematica's >>>> >> Binomial function: Some moron complained about the asymmetry so >>>> >> long after it was implemented that WRI forgot why it's asymmetrical, >>>> >> and accommodated the moron. >>>> > >>>> > For those of us who aren't familiar with all Mathematica's >>>> > quirks, would you care to say what erroneous symmetry Mma >>>> > gives to the binomial coefficients? >>>> > >>>> > (My apologies if this was already being discussed in some >>>> > other thread and I just missed it.) >>>> > >>>> > -- >>>> > g

1 0

Re: [math-fun] Stick to your guns.
by Henry Baker 23 Jul '17

23 Jul '17

Dropbox is a pain, unless you add "?dl=1" to the end, as in: https://www.dropbox.com/s/9vvl6l6ym1zkret/binomial.pdf?dl=1 The "?" indicates that you're passing parameters, and the "dl=1" says -- in essence -- "download equals 1 -- i.e., *yes*". It took me quite a while to figure this out about dropbox. At 06:16 PM 7/22/2017, Fred Lunnon wrote: > @#$%^&?! ... DropBox is getting steadily less user-friendly --- >why give me a link and immediately disable the infernal thing? >Anyway, I have copied the file, deleted it and re-up-loaded it: >try instead > > https://www.dropbox.com/s/9vvl6l6ym1zkret/binomial.pdf > >WFL > >On 7/23/17, Neil Sloane <njasloane(a)gmail.com> wrote: >> Fred, >> when I tried to look at your discussion, >> https://www.dropbox.com/s/anykne0pd55ehjg/binomial.pdf >> I got a rude "go away" message >> >> Best regards >> Neil >> >> Neil J. A. Sloane, President, OEIS Foundation. >> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. >> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. >> Phone: 732 828 6098; home page: http://NeilSloane.com >> Email: njasloane(a)gmail.com >> >> On Sat, Jul 22, 2017 at 7:20 PM, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: >> >>> See the note I wrote up following a discussion on this list circa 2014 >>> --- >>> https://www.dropbox.com/s/anykne0pd55ehjg/binomial.pdf >>> >>> [ I did contemplate trying to get this published in the Math. Intelligencer, >>> but retreated in the face of an editor's mysterious antipathy to computer- >>> generated illustrations. ] >>> >>> WFL >>> >>> On 7/22/17, Gareth McCaughan <gareth.mccaughan(a)pobox.com> wrote: >>> >> I'm guessing that a similar lapse of conviction ruined Mathematica's >>> >> Binomial function: Some moron complained about the asymmetry so >>> >> long after it was implemented that WRI forgot why it's asymmetrical, >>> >> and accommodated the moron. >>> > >>> > For those of us who aren't familiar with all Mathematica's >>> > quirks, would you care to say what erroneous symmetry Mma >>> > gives to the binomial coefficients? >>> > >>> > (My apologies if this was already being discussed in some >>> > other thread and I just missed it.) >>> > >>> > -- >>> > g

1 0

Re: [math-fun] Where do roots live in GF(2^k) ?
by Dan Asimov 23 Jul '17

23 Jul '17

It is very cool that matrix algebras act as some kind of universal systems in which all lesser algebras sit. —Dan >From: "W. Edwin Clark" <wclark(a)mail.usf.edu> >Sent: Jul 22, 2017 8:29 PM >Finite fields are finite dimensional associative algebras over their ground >fields (or any subfield). > >In general every n-dimensional associative algebra A over a field F, is >isomorphic >to a subalgebra of the algebra of all n x n matrices over F if A has an >identity--- >otherwise A can be embedded in an algebra with identity of dimension n + 1 >and >thus becomes a subalgebra of (n+1) x (n+1) matrices over F. > >On Sat, Jul 22, 2017 at 4:50 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: > >> Don't know if this helps, but: It occurred to me that maybe a finite field >> F(p^n) might possibly live as a subring of a matrix ring over its ground >> field F(p). Googling led to this paper, >> "Matrix representation of finite fields": >> >> http://www.dtic.mil/dtic/tr/fulltext/u2/a247828.pdf >> >> , which finds a generator for a finite fields as a matrix over the ground >> field. >> >> There's also a bunch more interesting stuff here about ways to represent >> fields (not necessarily visually) at "Topics in normal bases of finite >> fields": >> >> https://arxiv.org/pdf/1304.0420.pdf >> Henry Baker wrote: >> ----- >> OK, if I extend the rationals with the root alpha of an irreducible >> polynomial p[x], I can plot alpha on the complex plane; indeed, I can plot >> *all* of the roots of p[x] on the complex plane. So all of these "extension >> roots" live in the complex plane. >> >> Is there an analogous (single) place/field where all extension roots of >> GF(p) live -- i.e., a larger field which includes all of the extension >> fields of GF(p) ? >> >> There seems to be a problem, since there are many (isomorphic) ways to >> extend GF(p); perhaps these are all different in this larger field? >> -----

1 0

Re: [math-fun] Where do roots live in GF(2^k) ?
by Dan Asimov 23 Jul '17

23 Jul '17

Don't know if this helps, but: It occurred to me that maybe a finite field F(p^n) might possibly live as a subring of a matrix ring over its ground field F(p). Googling led to this paper, "Matrix representation of finite fields": http://www.dtic.mil/dtic/tr/fulltext/u2/a247828.pdf , which finds a generator for a finite fields as a matrix over the ground field. There's also a bunch more interesting stuff here about ways to represent fields (not necessarily visually) at "Topics in normal bases of finite fields": https://arxiv.org/pdf/1304.0420.pdf . —Dan Henry Baker wrote: ----- OK, if I extend the rationals with the root alpha of an irreducible polynomial p[x], I can plot alpha on the complex plane; indeed, I can plot *all* of the roots of p[x] on the complex plane. So all of these "extension roots" live in the complex plane. Is there an analogous (single) place/field where all extension roots of GF(p) live -- i.e., a larger field which includes all of the extension fields of GF(p) ? There seems to be a problem, since there are many (isomorphic) ways to extend GF(p); perhaps these are all different in this larger field? -----

2 1