pith. sign in

arxiv: 1907.08675 · v1 · pith:OW5PIABXnew · submitted 2019-07-17 · 🧮 math.NT

On the linking of number lattices

H. Narayanan , Hariharan Narayanan This is my paper

Pith reviewed 2026-05-24 20:34 UTC · model grok-4.3

classification 🧮 math.NT
keywords number latticesgeneralized number latticesmatched compositionimplicit duality theoremself-dual latticesreduced baseslinking operationdual lattices
0
0 comments X

The pith

The linking operation on generalized number lattices satisfies an implicit duality theorem that preserves duals and enables new self-dual constructions along with efficient reduced basis algorithms.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces the linking, or matched composition, of generalized number lattices, which are sums of number lattices and vector spaces. It proves an implicit duality theorem showing that the dual of a linked pair equals the link of the duals, and an implicit inversion theorem for when repeated linking recovers the original. These results allow constructing new self-dual lattices from existing ones and provide algorithms for reduced bases of linked structures and their duals when the vector space has a totally unimodular basis satisfying the inversion condition. Readers interested in lattice theory would care because the methods transfer concepts from network theory to simplify computations and constructions in number lattices.

Core claim

The paper claims that for generalized number lattices K_SP and K_P, the matched composition satisfies (K_SP ↔ K_P)^d = K_SP^d ↔ K_P^d, and given V_SP with totally unimodular basis where V_SP ↔ (V_SP ↔ K_P) = K_P, there exist efficient algorithms to construct reduced bases for the number lattice part of V_SP ↔ K_P, its dual, and K_P's dual from a reduced basis of K_P. It also shows simple methods to construct new self-dual lattices using the duality theorem.

What carries the argument

The matched composition operation K_SP ↔ K_P, defined as the set of S-components from pairs in K_SP whose P-components lie in K_P, which interacts with duality and inversion.

Load-bearing premise

The vector space part V_SP of the generalized lattice has a totally unimodular basis and satisfies the equality V_SP ↔ (V_SP ↔ K_P) = K_P.

What would settle it

Finding specific generalized number lattices K_SP and K_P where the dual of their matched composition differs from the matched composition of their duals would falsify the implicit duality theorem.

read the original abstract

In this paper we study ideas which have proved useful in topological network theory in the context of lattices of numbers. A number lattice $L_S$ is a collection of row vectors, over $\mathbb{Q}$ on a finite column set $S,$ generated by integral linear combination of a finite set of row vectors. A generalized number lattice $K_S$ is the sum of a number lattice $L_S$ and a vector space $V_S$ which has only the zero vector in common with it. The dual $K^d_S$ of a generalized number lattice is the collection of all vectors whose dot product with vectors in $K_S$ are integral and is another generalized number lattice. We consider a linking operation ('matched composition`) between generalized number lattices $K_{SP},K_{P}$ (regarded as collections of row vectors on column sets $S\cup P, P,$ respectively with $S,P,$ disjoint) defined by $K_{SP}\leftrightarrow K_{P}\equiv \{f_S:((f_S,g_P)\in K_{SP}, g_P \in K_{P}\}.$ We show that this operation together with contraction and restriction, and the results, the implicit inversion theorem (which gives simple conditions for the equality $K_{SP}\leftrightarrow (K_{SP}\leftrightarrow K_S)= K_S,$ to hold) and implicit duality theorem ($(K_{SP}\leftrightarrow K_{P})^d= K_{SP}^d\leftrightarrow K_{P}^d$)), are both relevant and useful in suggesting problems concerning number lattices and their solutions. Using the implicit duality theorem, we give simple methods of constructing new self dual lattices from old. We also give new and efficient algorithms for the following. Given $V_{SP},K_P,$ such that $V_{SP}\leftrightarrow (V_{SP}\leftrightarrow K_P)= K_P,$ where $V_{SP}$ is a vector space with a totally unimodular basis matrix, to construct reduced bases for the number lattice part of $V_{SP}\leftrightarrow K_P, K_P^d, (V_{SP}\leftrightarrow K_P)^d,$ from a reduced basis for the number lattice part of $K_P.$

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines number lattices L_S as Z-linear combinations of row vectors over Q on finite column set S, and generalized number lattices K_S as L_S + V_S with trivial intersection. It introduces a linking (matched composition) operation K_SP ↔ K_P on disjoint column sets, proves an implicit inversion theorem giving conditions for K_SP ↔ (K_SP ↔ K_S) = K_S, and an implicit duality theorem (K_SP ↔ K_P)^d = K_SP^d ↔ K_P^d. These are used to construct new self-dual lattices from old ones and to give algorithms that, given V_SP with totally unimodular basis satisfying V_SP ↔ (V_SP ↔ K_P) = K_P, produce reduced bases for the number-lattice parts of V_SP ↔ K_P, K_P^d and (V_SP ↔ K_P)^d from a reduced basis of K_P.

Significance. If the theorems and algorithms hold under the stated hypotheses, the work supplies explicit, condition-dependent constructions for self-dual lattices and reduced-basis algorithms that rely only on standard duals and the new linking operation. This could be useful for explicit computations with integer lattices in number theory. The explicit conditioning of the algorithms on the totally-unimodular-basis and inversion hypotheses is a strength, as is the derivation of the duality theorem from the linking definition.

major comments (2)
  1. [implicit duality theorem statement] The central claim that the implicit duality theorem holds for the linking operation is load-bearing for both the self-dual-lattice constructions and the reduced-basis algorithms, yet the abstract provides no indication of the precise hypotheses (e.g., whether the vector-space summands must be complementary in a stronger sense) under which the equality (K_SP ↔ K_P)^d = K_SP^d ↔ K_P^d is proved; a concrete counter-example or missing hypothesis would undermine the applications in § on self-dual lattices and the algorithmic section.
  2. [algorithmic results paragraph] The reduced-basis algorithm is stated only under the premise V_SP ↔ (V_SP ↔ K_P) = K_P together with the totally-unimodular-basis condition on V_SP; if this premise is not automatically satisfied for the lattices arising from the earlier constructions, the algorithmic claim is conditional rather than unconditional and its scope must be clarified.
minor comments (2)
  1. [definition of linking] Notation for the linking operation uses both ↔ and the textual phrase 'matched composition'; a single consistent symbol or definition block would improve readability.
  2. [abstract] The abstract refers to 'the results, the implicit inversion theorem … and implicit duality theorem' without numbering or cross-references; adding theorem labels would help readers locate the statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation of minor revision. We respond to the two major comments point by point.

read point-by-point responses

  1. Referee: [implicit duality theorem statement] The central claim that the implicit duality theorem holds for the linking operation is load-bearing for both the self-dual-lattice constructions and the reduced-basis algorithms, yet the abstract provides no indication of the precise hypotheses (e.g., whether the vector-space summands must be complementary in a stronger sense) under which the equality (K_SP ↔ K_P)^d = K_SP^d ↔ K_P^d is proved; a concrete counter-example or missing hypothesis would undermine the applications in § on self-dual lattices and the algorithmic section.

    Authors: The implicit duality theorem is proved in the body of the paper directly from the definition of the linking operation and the standard definition of generalized number lattices (K_S = L_S + V_S with L_S ∩ V_S = {0}). No stronger complementarity condition on the summands is required or used. We agree the abstract should indicate the hypotheses and will revise it accordingly to state that the theorem holds under these definitions. revision: yes

  2. Referee: [algorithmic results paragraph] The reduced-basis algorithm is stated only under the premise V_SP ↔ (V_SP ↔ K_P) = K_P together with the totally-unimodular-basis condition on V_SP; if this premise is not automatically satisfied for the lattices arising from the earlier constructions, the algorithmic claim is conditional rather than unconditional and its scope must be clarified.

    Authors: The algorithms are explicitly conditional on the stated premise (which is guaranteed by the implicit inversion theorem) together with the totally unimodular condition. We will add a clarifying remark in the algorithmic section explaining that the premise holds for the lattices obtained from the self-dual constructions via the inversion theorem, thereby making the scope explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; theorems follow from definitions

full rationale

The paper defines number lattices, generalized number lattices, duals, and the linking operation ('matched composition'), then states the implicit inversion theorem and implicit duality theorem as results shown to hold under these constructions. The reduced-basis algorithms are explicitly conditioned on the premises that V_SP has a totally unimodular basis and satisfies V_SP ↔ (V_SP ↔ K_P) = K_P; these premises are supplied rather than derived from the outputs. No equations reduce by construction to their inputs, no fitted parameters are renamed as predictions, and no load-bearing self-citations appear in the abstract or described chain. The derivation is self-contained against the stated definitions and standard dual properties.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The work rests on standard linear algebra over Q together with newly introduced definitions of generalized lattices and the linking operation; no free parameters are fitted to data.

axioms (2)
  • standard math Vector spaces and lattices over Q with integral-valued dot products defining duality
    Invoked throughout the definitions of duals and linking.
  • domain assumption Existence of totally unimodular basis matrices for the vector spaces in the algorithmic claims
    Required for the reduced-basis algorithms stated in the abstract.
invented entities (1)
  • Matched composition (linking) operation no independent evidence
    purpose: To combine generalized number lattices on disjoint column sets while preserving lattice structure
    Newly defined operation central to the inversion and duality theorems

pith-pipeline@v0.9.0 · 5942 in / 1377 out tokens · 27221 ms · 2026-05-24T20:34:28.441430+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Arora, L

    S. Arora, L. Babai, J. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, J. Comput. Syst. Sci. 54.(1997) 317–331

    work page 1997

  2. [2]

    Babai, On Lovasz lattice reduction and the nearest lattice point problem

    L. Babai, On Lovasz lattice reduction and the nearest lattice point problem. Combinatorica , 6(1):(1986) 1–13

    work page 1986

  3. [3]

    Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Mathematische Annalen, 296(4):625635, 1993

    W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Mathematische Annalen, 296(4):625635, 1993

    work page 1993

  4. [4]

    J. W. S. Cassels. An introduction to the geometry of numbers . Springer-Verlag, New York, 1971

    work page 1971

  5. [5]

    J. D. Dixon, Exact Solution of Linear Equations Using p-Adic Expansions, Numer. Math. (40) (1982) 137–141

    work page 1982

  6. [6]

    G. D. Forney, M. D. Trott, The Dynamics of Group Codes : Dual Abelian Group Codes and Systems, IEEE Transactions on Information Theory 50 (11) (2004) 1–30

    work page 2004

  7. [7]

    J. L. Hafner and K. S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068–1083

    work page 1991

  8. [8]

    Kannan, Algorithmic Geometry of numbers, Annual Reviews of Computer Science, 2 (1987) 231–267

    R. Kannan, Algorithmic Geometry of numbers, Annual Reviews of Computer Science, 2 (1987) 231–267. Annual Review Inc. , Palo Alto, California

    work page 1987

  9. [9]

    Khot, Hardness of approximating the shortest vector problem in lattices, J

    S. Khot, Hardness of approximating the shortest vector problem in lattices, J. ACM. 52 (2005) 789–808

    work page 2005

  10. [10]

    J. C. Lagarias, H. W. Lenstra, Jr., and C. P. Schnorr. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, 10 (1990) 333–348

    work page 1990

  11. [11]

    J. K. Lenstra, H. W. Lenstra and L. Lovasz, Factoring polynomials with rational coeffidents, Math. Ann. 261 (1982), 515–534

    work page 1982

  12. [12]

    Micciancio and S

    D. Micciancio and S. Goldwasser. Complexity of Lattice Problems: a cryptographic perspective , Kluwer Academic Publishers, Boston, Massachusetts, 2002

    work page 2002

  13. [13]

    Micciancio

    D. Micciancio. Lecture notes on lattice algorithms and applications, 2014. Available at http://cseweb.ucsd.edu/ daniele/classes.html, last accessed 17 Oct 2014

    work page 2014

  14. [14]

    Narayanan, On the decomposition of vector spaces, Linear Algebra and its Applications 76 (1986) 61–98

    H. Narayanan, On the decomposition of vector spaces, Linear Algebra and its Applications 76 (1986) 61–98

    work page 1986

  15. [15]

    Narayanan, A Unified Construction of Adjoint Systems and Networks, Circuit Theory and Applications 14 (1986) 263–276

    H. Narayanan, A Unified Construction of Adjoint Systems and Networks, Circuit Theory and Applications 14 (1986) 263–276

    work page 1986

  16. [16]

    Narayanan, Topological transformations of electrical networks, International Journal of Circuit Theory and Applications 15 (3) (1987) 211–233

    H. Narayanan, Topological transformations of electrical networks, International Journal of Circuit Theory and Applications 15 (3) (1987) 211–233

    work page 1987

  17. [17]

    H. Narayanan, Some applications of an implicit duality theorem to connections of structures of special types including dirac and reciprocal structures, Systems & Control Letters 45 (2) (2002) 87 – 95

    work page 2002

  18. [18]

    Narayanan, Submodular Functions and Electrical Networks, Annals of Discrete Mathematics, vol

    H. Narayanan, Submodular Functions and Electrical Networks, Annals of Discrete Mathematics, vol. 54, North Holland, Amsterdam, 1997. (Open 2nd edition, http://www.ee.iitb.ac.in/˜ hn/ , 2009.)

    work page 1997

  19. [19]

    Narayanan, On the Duality between Controllability and Observability in Behavioural Systems Theory, Proc

    H. Narayanan, On the Duality between Controllability and Observability in Behavioural Systems Theory, Proc. Inter- national Conference on Communications Control and Signal Processing, CCSP 2000, Bangalore, July 25-July 28,2000, 183–186. (https://www.ee.iitb.ac.in/ hn/otherpapers.htm)

    work page 2000

  20. [20]

    Narayanan, Matroids representable over Modules, Electrical Network Topology and Behavioural Systems Theory, Research report of the EE Dept., IIT Bombay, May 2000

    H. Narayanan, Matroids representable over Modules, Electrical Network Topology and Behavioural Systems Theory, Research report of the EE Dept., IIT Bombay, May 2000. (https://www.ee.iitb.ac.in/ hn/otherpapers.htm)

    work page 2000

  21. [21]

    C. Peikert. A decade of lattice cryptography, Cryptology ePrint Archive, Report 2015/939, 2015. http://eprint.iacr.org/

    work page 2015

  22. [22]

    Nguyen and D

    Phong Q. Nguyen and D. Stehle, An LLL algorithm with quadratic complexity, Siam J. Comput. (39) (2009) 874–903

    work page 2009

  23. [23]

    Regev, Lattices in computer science, Lecture notes of a course given in Tel Aviv University (2004)

    O. Regev, Lattices in computer science, Lecture notes of a course given in Tel Aviv University (2004)

    work page 2004

  24. [24]

    Narayanan, On the notion of generalized minor in topological network theory and matroids, Linear Algebra and its Applications 458 (2014) 1–46

    Siva Theja, H. Narayanan, On the notion of generalized minor in topological network theory and matroids, Linear Algebra and its Applications 458 (2014) 1–46

    work page 2014

  25. [25]

    Storjohann and G

    A. Storjohann and G. Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices, ISSAC’96 (Zurich,Switzerland,1996),ACM, 259–266

    work page 1996

  26. [26]

    Storjohann, On the complexity of inverting integer and polynomial matrices, Computational Complexity, (24) (2015) 777–821

    A. Storjohann, On the complexity of inverting integer and polynomial matrices, Computational Complexity, (24) (2015) 777–821

    work page 2015

  27. [27]

    W. T. Tutte, Lectures on matroids, Journal of Research of the National Bureau of Standards, vol. B69 (1965) 1–48. 34

    work page 1965