[math-fun] Companion manifolds
Maybe Christmas is not a good time to float the indigestible screed below --- but it's what I've got on the brain at the moment, so here goes! WFL Companion manifolds --- I am interested in a certain family of algebraic manifolds, call them J(S), with components ranging over some finite field \F_q. The question arises, given that J(S) is a singular scroll of dimension 2, can the number of points on it be bounded in terms of q? What can be said more generally about its geometry? I have so far explored J(S) for 2 points S over \F_2, having 6,8 points more (besides S) resp; and 1 point over \F_3, having 24 points more. [OK, I know this doesn't look very impressive --- but the software was a pig to develop!] Definition of J(S) --- {X_ij | i,j in \Z} denotes a two-dimensional array of variables; S = [S_ij], T, U denote points in the corresponding \N-dimensional projective space I. A^ij denote "cruciform" matrices such that (A^ij)_kl = 1 for (k,l) = (i,j); -1 for (k,l) = (i-1,j), (i+1,j), (i,j-1), (i,j+1); 0 otherwise, for k,l in \Z. K denotes the \N-dimensional manifold intersecting the set of quadrics {T' (A^ij) T = 0 | i,j in \Z}; given some point S on K, J(S) denotes the manifold intersecting K with the set of flats {S' (A^ij) T = 0 | i,j in \Z} [where X' denotes transpose]. Lemma --- J(S) is the union of (all points on) a set of lines through its "vertex" S. For if X = aS + bT is an arbitrary point on the line joining S,T, easily X' (A^ij) X = a^2 S' (A^ij) S + 2ab(S' (A^ij) T) + b^2 T' (A^ij) T = 0, so X also lies on J(S). Syzygy --- Among the "2-diamond" set of 15 equations in 26 variables {S' (A^ij) S = 0 | (i,j) = (0,0), (-1,0), (0,-1), (+1,0), (0,+1)} U {T' (A^ij) T = 0 | (i,j) = (0,0), (-1,0), (0,-1), (+1,0), (0,+1)} U {S' (A^ij) T = 0 | (i,j) = (0,0), (-1,0), (0,-1), (+1,0), (0,+1)} any one is implied by the remaining 14. [The syzygy relation is omitted.] Geometrically, it follows for instance that a line lying on four such quadrics, and passing through 2 points of the fifth, must also lie on the fifth. Theorem --- J(S) has dimension two. Proof: Given n in \N, consider the finite "n-diamond" section of I defined by {X_ij | |i|+|j| < n}; the number of components in this set equals m(n) = (1 + 3 + ... + (2n+1) + ... + 3 + 1) = 2(n+1)n + 1; the number of quadrics (1-diamonds) involving only these components equals m(n-1); the number of 5-quadric sets (2-diamonds) equals m(n-2). Within this section, an arbitrary point has freedom d = m(n)-1, losing 1 for each quadric to which it is constrained; so a point on K has freedom e = m(n)-1 - m(n-1). An arbitrary line has freedom 2(d-1), losing 3 for each quadric to which it is constrained, but gaining 1 for each 2-diamond via the syzygy; so a line on K has freedom f = 2m(n)-4 - 3m(n-1) + m(n-2). Finally, the dimension of J(S) equals f+1 - e = 2m(n)-4 - 3m(n-1) + m(n-2) + 1 - m(n)+1 + m(n-1) = m(n) - 2m(n-1) + m(n-2) - 2 = 4-2 = 2. Now let n -> oo. QED. Critique --- A number of features of the argument above are of dubious provenance. In what sense can the space I and manifold K be said to exist at all, as entities on which it might be legitimate to perform algebraic geometry? The ground field is discrete; and even if it were continuous, there is no apparent metric (as is available for example in Hilbert space). In particular, under what circumstances is it possible to justify letting n -> oo ? In particular cases the denumerable dimension can be circumvented: for instance, if S is singly- or doubly-periodic, the array of variables may be wrapped around into a cylinder or torus; and if the points involved have zero components for sufficently large |i| or |j| or both, the array may be truncated at that bound. Plainly, such stratagems are theoretically undesirable. In any case, bearing in mind the translation symmetry of the equation system for K, it in practice usually proves sufficient to consider a single 2-diamond. Again, the argument implicitly assumes that all points S on K are equivalent. Each quadric is invariant under some conjugate of a mixed orthogonal group; but it's far from clear whether the intersection of these is transitive on the points of K. Motivation --- A "number wall" is most easily thought of as a difference table on steroids, allowing an LFSR sequence to be detected, interpolated etc. in much the same way as the latter serves a polynomial sequence: in this initial incarnation, the number wall is the 2-D array of persymmetric determinants formed from sub-blocks of the given sequence. The 2001 paper gave identities permitting recursive numerical computation of a number wall in the presence of square "windows" of zero components; for these "frame theorems" it provided an involved and delicate inductive proof relying on a deal of intrusive analytical machinery. A purely algebraic approach circumvents most of this complexity, as well as tying up a number of loose ends in the earlier treatment. The price to be paid is the transmogrification of a number wall (modulo a constant factor) into a point S in the alarmingly large manifold K above. Having grasped this nettle, we are rewarded in an astonishing fashion. Each wall S is the vertex of a scroll J(S) of lines, on which every point T represents another "companion" wall. For each companion T, its windows are centred on the same locations as those of S, but may either swell (increase in size by 2), stick (remain unchanged), or shrink (decrease by 2). Choosing a T for which a given window shrinks allows it to be perturbed in a linear fashion, in turn reducing the inductive proof mentioned earlier to elementary algebra. W. F. Lunnon "The Number-Wall Algorithm: an LFSR Cookbook" Article 01.1.1 Journal of Integer Sequences, Vol. 4 (2001) http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LUNNON/numbwall10.html Fred Lunnon [Maynooth 19/12/08]
Corrections and clarifications, courtesy of Dan Asimov --- On 12/19/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Companion manifolds ---
I am interested in a certain family of algebraic manifolds, call them J(S), with components ranging over some finite field \F_q. The question arises, given that J(S) is a singular scroll of dimension 2, can the number of points on it be bounded in terms of q? What can be said more generally about its geometry?
I have so far explored J(S) for 2 points S over \F_2, having 6,8 points more (besides S) resp; and 1 point over \F_3, having 24 points more. [OK, I know this doesn't look very impressive --- but the software was a pig to develop!]
The components might in principle be taken from any ground field --- I'm looking at components in Fermat fields \F_2 or \F_3 at the moment, partly because they're the most relevant to applications in cryptography, and partly because it's easier to process the results, compared \Q or \R. I'm pretty certain that people regularly do geometry over \F_p, but what they call such analogues of real projective space I don't know --- \F_p P^\N maybe?
Definition of J(S) ---
{X_ij | i,j in \Z} denotes a two-dimensional array of variables; S = [S_ij], T, U denote points in the corresponding \N-dimensional projective space I. A^ij denote "cruciform" matrices such that (A^ij)_kl = 1 for (k,l) = (i,j); -1 for (k,l) = (i-1,j), (i+1,j), (i,j-1), (i,j+1); 0 otherwise, for k,l in \Z. K denotes the \N-dimensional manifold intersecting the set of quadrics {T' (A^ij) T = 0 | i,j in \Z}; given some point S on K, J(S) denotes the manifold intersecting K with the set of flats {S' (A^ij) T = 0 | i,j in \Z} [where X' denotes transpose].
All I was trying to say was that each quadratic equation of the form X' (A^ij) X = 0 defines a primal quadric in I; their intersection for all (i,j) defines the manifold K, with both dimension and codimension equal to \N.
Lemma ---
J(S) is the union of (all points on) a set of lines through its "vertex" S. For if X = aS + bT is an arbitrary point on the line joining S,T, easily X' (A^ij) X = a^2 S' (A^ij) S + 2ab(S' (A^ij) T) + b^2 T' (A^ij) T = 0, so X also lies on J(S).
Syzygy ---
Among the "2-diamond" set of 15 equations in 26 variables {S' (A^ij) S = 0 | (i,j) = (0,0), (-1,0), (0,-1), (+1,0), (0,+1)} U {T' (A^ij) T = 0 | (i,j) = (0,0), (-1,0), (0,-1), (+1,0), (0,+1)} U {S' (A^ij) T = 0 | (i,j) = (0,0), (-1,0), (0,-1), (+1,0), (0,+1)} any one is implied by the remaining 14. [The syzygy relation is omitted.] Geometrically, it follows for instance that a line lying on four such quadrics, and passing through 2 points of the fifth, must also lie on the fifth.
Theorem ---
J(S) has dimension two. Proof: Given n in \N, consider the finite "n-diamond" section of I defined by {X_ij | |i|+|j| < n}; the number of components in this set equals m(n) = (1 + 3 + ... + (2n+1) + ... + 3 + 1) = 2(n+1)n + 1; the number of quadrics (1-diamonds) involving only these components equals m(n-1); the number of 5-quadric sets (2-diamonds) equals m(n-2).
Within this section, an arbitrary point has freedom d = m(n)-1, losing 1 for each quadric to which it is constrained; so a point on K has freedom e = m(n)-1 - m(n-1). An arbitrary line has freedom 2(d-1), losing 3 for each quadric to which it is constrained, but gaining 1 for each 2-diamond via the syzygy; so a line on K has freedom f = 2m(n)-4 - 3m(n-1) + m(n-2).
Finally, the dimension of J(S) equals f+1 - e = 2m(n)-4 - 3m(n-1) + m(n-2) + 1 - m(n)+1 + m(n-1) = m(n) - 2m(n-1) + m(n-2) - 2 = 4-2 = 2. Now let n -> oo. QED.
Critique ---
A number of features of the argument above are of dubious provenance. In what sense can the space I and manifold K be said to exist at all, as entities on which it might be legitimate to perform algebraic geometry? The ground field is discrete; and even if it were continuous, there is no apparent metric (as is available for example in Hilbert space). In particular, under what circumstances is it possible to justify letting n -> oo ?
In particular cases the denumerable dimension can be circumvented: for instance, if S is singly- or doubly-periodic, the array of variables may be wrapped around into a cylinder or torus; and if the points involved have zero components for sufficently large |i| or |j| or both, the array may be truncated at that bound. Plainly, such stratagems are theoretically undesirable. In any case, bearing in mind the translation symmetry of the equation system for K, it in practice usually proves sufficient to consider a single 2-diamond.
Again, the argument implicitly assumes that all points S on K are equivalent. Each quadric is invariant under some conjugate of a mixed orthogonal group; but it's far from clear whether the intersection of these is transitive on the points of K.
Motivation --- A "number wall" is most easily thought of as a difference table on steroids, allowing an LFSR sequence to be detected, interpolated etc. in much the same way as the latter serves a polynomial sequence: in this initial incarnation, the number wall is the 2-D array of persymmetric determinants formed from sub-blocks of the given sequence.
The 2001 paper gave identities permitting recursive numerical computation of a number wall in the presence of square "windows" of zero components; for these "frame theorems" it provided an involved and delicate inductive proof relying on a deal of intrusive analytical machinery. A purely algebraic approach circumvents most of this complexity, as well as tying up a number of loose ends in the earlier treatment. The price to be paid is the transmogrification of a number wall (modulo a constant factor) into a point S in the alarmingly large manifold K above.
Having grasped this nettle, we are rewarded in an astonishing fashion. Each wall S is the vertex of a scroll J(S) of lines, on which every point T represents another "companion" wall. For each companion T, its windows are centred on the same locations as those of S, but may either swell (increase in size by 2), stick (remain unchanged), or shrink (decrease by 2). Choosing a T for which a given window shrinks allows it to be perturbed in a linear fashion, in turn reducing the inductive proof mentioned earlier to elementary algebra.
W. F. Lunnon "The Number-Wall Algorithm: an LFSR Cookbook" Article 01.1.1 Journal of Integer Sequences, Vol. 4 (2001) http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LUNNON/numbwall10.html
Fred Lunnon [Maynooth 19/12/08]
Following further trenchant observations from Dan, I conclude that introducing geometry at the start of this discussion may have been a mistake. [Not to mention committing a truly horrible typo in defining the matrices, over which I managed to confuse myself as much as everybody else --- I'm good at that!] So for now I'll just talk about polynomials with coefficients in some field --- usually \F_p for p = 2,3 in practice. My set of variables is X_(i,j), S_(i,j) where i,j in \Z, the subscript range being |i|+|j| <= n, with n remaining deliberately unspecified. My homogeneous quadratic forms are G_(i,j)(X) = X_(i,j) ^2 - X_(i-1,j) X_(i+1,j) - X_(i,j-1) X_(i,j+1), and the corresponding bilinear H_(i,j)(X,S) = 2 X_(i,j) S_(i,j) - X_(i-1,j) S_(i+1,j) - X_(i,j-1) S_(i,j+1) - S_(i-1,j) X_(i+1,j) - S_(i,j-1) X_(i,j+1). [We mustn't G_(i,j)(X) = (1/2)H_(i,j)(X,X) in case p = 2.] Now assign some appropriate numerical values to S, and consider the set J(S) = {X | G_(i,j)(X) = H_(i,j)(X,S) = G_(i,j)(S) = 0} for all |i|+|j| < n. I can prove that the dimension of J(S) equals 2. [Dimension is defined here algebraically, as n-1 less the least cardinal of any basis of the ideal whose zero set defines the algebraic variety.] Taking p = 3 for instance, examination of actual values assigned to S suggests that the number of "points" in J(S) is usually 24. [Points are solutions, not all zero, and modulo constant factors --- {-1,+1} in the case of p = 3.] Question: is it possible to actually prove this sort of result; or otherwise to bound the number of points in J(S)? Third time lucky, I hope! Fred Lunnon
On 12/22/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
... Question: is it possible to actually prove this sort of result; or otherwise to bound the number of points in J(S)?
Third time lucky, I hope! Fred Lunnon
Hmm ... keep hoping! To those hanging on my every word regarding this comedy of errors, a quick update :--- The n-diamond comprises {X_ij | |i|+|j| <= n}, rather than ... < ... The dimension of the companion cone J(S) equals (f+1) - (e-1), so not 2 but 3 --- a result confirmed by another simpler argument, earlier discounted since it seemd meaningful only over continuous ground domains. As a consequence of the fact that J(S) is determined locally by any (sufficiently large) finite subset of the components, its point count is independent of the chosen vertex S; hence it can be computed by examining case of S the wall of the zero sequence (a single row of units), for which easily: The number of lines in J(S), all meeting in the vertex S, equals (p^2-1); The number of points (excluding S) equals (p^2-1)(p-1); The number of walls (properly) companion to S equals (p^2-1)(p-1)^2. Compare the J(S) (inclusive) point count p^3 - p^2 - p + 2, with the 3-flat point count p^3 + p^2 + p + 1; we expect the former to be somewhat reduced on account of the singularity at S. Might J(S) be something quite simple, such as a quadric cone? What about a parametric presentation for it? I have quite a few examples of these things now, but shan't bother posting them unless requested. Fred Lunnon
participants (1)
-
Fred lunnon