2025-11-16T05:37:12.390311

The asymptotic number of equivalence classes of linear codes with given dimension

Di Giusto, Ravagnani
We investigate the asymptotic number of equivalence classes of linear codes with prescribed length and dimension. While the total number of inequivalent codes of a given length has been studied previously, the case where the dimension varies as a function of the length has not yet been considered. We derive explicit asymptotic formulas for the number of equivalence classes under three standard notions of equivalence, for a fixed alphabet size and increasing length. Our approach also yields an exact asymptotic expression for the sum of all q-binomial coefficients, which is of independent interest and answers an open question in this context. Finally, we establish a natural connection between these asymptotic quantities and certain discrete Gaussian distributions arising from Brownian motion, providing a probabilistic interpretation of our results.
academic

Die asymptotische Anzahl von Äquivalenzklassen linearer Codes mit gegebener Dimension

Grundinformationen

  • Papier-ID: 2510.14424
  • Titel: The asymptotic number of equivalence classes of linear codes with given dimension
  • Autoren: Andrea Di Giusto (Technische Universität Eindhoven), Alberto Ravagnani (Technische Universität Eindhoven)
  • Klassifikation: cs.IT (Informationstheorie), math.CO (Kombinatorik), math.IT (Mathematische Informationstheorie)
  • Veröffentlichungsdatum: 16. Oktober 2025 (arXiv-Preprint)
  • Papierlink: https://arxiv.org/abs/2510.14424

Zusammenfassung

In diesem Papier wird die asymptotische Anzahl von Äquivalenzklassen linearer Codes mit gegebener Länge und Dimension untersucht. Obwohl die Gesamtzahl nicht-äquivalenter Codes bei gegebener Länge bereits erforscht wurde, wurde der Fall, in dem die Dimension als Funktion der Länge variiert, bisher nicht berücksichtigt. Die Autoren leiten unter drei standardisierten Äquivalenzkonzepten explizite asymptotische Formeln für die Anzahl der Äquivalenzklassen bei fester Alphabetgröße und wachsender Länge her. Das Verfahren liefert auch exakte asymptotische Ausdrücke für die Summen aller q-Binomialkoeffizienten, was eigenständigen Wert hat und ein offenes Problem in diesem Bereich beantwortet. Abschließend wird eine natürliche Verbindung zwischen diesen asymptotischen Größen und bestimmten diskreten Gaußverteilungen, die durch die Brownsche Bewegung entstehen, etabliert, was eine probabilistische Interpretation der Ergebnisse ermöglicht.

Forschungshintergrund und Motivation

Kernproblem

Das Kernproblem, das in diesem Papier gelöst werden soll, lautet: Wie verhält sich die asymptotische Anzahl von Äquivalenzklassen, wenn die Dimension k linearer Codes als Funktion der Codlänge n, nämlich k(n), variiert?

Bedeutung des Problems

  1. Theoretische Vollständigkeit: Füllt eine wichtige theoretische Lücke in der Codierungstheorie. Frühere Forschungen konzentrierten sich hauptsächlich auf die Gesamtzahl der Äquivalenzklassen aller Dimensionen bei fester Länge und ignorierten den Fall, in dem die Dimension mit der Länge variiert.
  2. Praktischer Anwendungswert: In praktischen Anwendungen muss die Dimension eines Codes häufig entsprechend der Codlänge angepasst werden, um spezifische Leistungsanforderungen zu erfüllen. Daher hat die Untersuchung der Anzahl von Äquivalenzklassen, wenn die Dimension mit der Länge variiert, wichtige praktische Bedeutung.
  3. Mathematische Bedeutung: Diese Forschung verbindet Codierungstheorie, Kombinatorik und Wahrscheinlichkeitstheorie, insbesondere diskrete Gaußverteilungen im Zusammenhang mit der Brownschen Bewegung.

Einschränkungen bestehender Methoden

  • Wild (2000): Untersuchte die Anzahl der Monomial-Äquivalenzklassen binärer Codes, aber der Beweis enthielt Lücken
  • Lax (2004): Entdeckte Probleme in Wilds Beweis
  • Hou (2005, 2007, 2009): Lieferte korrekte Beweise und erhielt asymptotische Formeln für die Gesamtzahl der Äquivalenzklassen, berücksichtigte aber nicht den Fall mit eingeschränkter Dimension

Die Haupteinschränkung bestehender Forschungen liegt darin, dass nur die Gesamtzahl der Äquivalenzklassen von Codes aller möglichen Dimensionen betrachtet wurde, in der Form: Nn∼∑j=0n(nj)qn!(q−1)n−1N_n \sim \frac{\sum_{j=0}^n \binom{n}{j}_q}{n!(q-1)^{n-1}}

aber nicht die Anzahl der Äquivalenzklassen Nk(n),nN_{k(n),n} bei Dimension k = k(n).

Kernbeiträge

  1. Etablierung asymptotischer Formeln für dimensionsbeschränkte Äquivalenzklassen: Für Dimensionsfunktionen k(n), die Bedingung (⋆) erfüllen, werden exakte asymptotische Ausdrücke unter drei Äquivalenzrelationen gegeben
  2. Lösung des offenen Problems der q-Binomialkoeffizientensummen: Liefert das exakte asymptotische Verhalten von S(n)=∑k=0n(nk)qS(n) = \sum_{k=0}^n \binom{n}{k}_q und beantwortet ein 2000 von Wild gestelltes offenes Problem
  3. Etablierung der Verbindung zu diskreten Gaußverteilungen: Entdeckt, dass das asymptotische Verhalten der Äquivalenzklassenverhältnisse mit den Jacobi-θ₂- und θ₃-Verteilungen zusammenhängt und liefert eine probabilistische Interpretation
  4. Vereinheitlichung von drei Äquivalenzkonzepten: Beweist, dass die Äquivalenzklassenverhältnisse unter Permutationsäquivalenz, Monomial-Äquivalenz und semilinearer Äquivalenz dasselbe asymptotische Verhalten aufweisen

Methodische Details

Aufgabendefinition

Gegeben:

  • Endlicher Körper Fq\mathbb{F}_q, wobei q eine Primzahlpotenz ist
  • Codlänge n und Dimensionsfunktion k(n)
  • Drei Äquivalenzrelationen: Permutationsäquivalenz (SnS_n), Monomial-Äquivalenz (MnM_n), semilineare Äquivalenz (Γn\Gamma_n)

Ziel: Bestimmung des asymptotischen Verhaltens der Anzahl der Äquivalenzklassen Nk(n),nGN^G_{k(n),n}, wobei G ∈ {S, M, Γ}

Grundlegendes Methodengerüst

1. Anwendung des Burnside-Lemmas

Für eine Gruppe G, die auf einer Menge X wirkt, ist die Anzahl der Äquivalenzklassen: ∣X/G∣=1∣G∣∑g∈G∣Fix(g,X)∣=∣Δ(G,X)∣∣X∣∣G∣+∑g∈G∖Δ(G,X)∣Fix(g,X)∣|X/G| = \frac{1}{|G|}\sum_{g \in G}|\text{Fix}(g,X)| = \frac{|\Delta(G,X)||X|}{|G|} + \sum_{g \in G\setminus\Delta(G,X)}|\text{Fix}(g,X)|

wobei Δ(G,X)={g∈G∣∀x∈X,g.x=x}\Delta(G,X) = \{g \in G | \forall x \in X, g.x = x\} der Kern der Wirkung ist.

2. Einführung von Bedingung (⋆)

Kritische technische Bedingung: Es existieren positive Konstanten A, ε, so dass lim⁡n→∞14n2−εn+An−k(n)(n−k(n))=−∞\lim_{n \to \infty} \frac{1}{4}n^2 - εn + A\sqrt{n} - k(n)(n-k(n)) = -\infty

Diese Bedingung stellt sicher, dass die Anzahl der Fixpunkte nicht-trivialer Gruppenelemente in der asymptotischen Analyse vernachlässigt werden kann.

3. Asymptotische Analyse der q-Binomialkoeffizienten

Etablierung der kritischen asymptotischen Beziehung: (nk(n))q∼1Kq(k(n))qk(n)(n−k(n))\binom{n}{k(n)}_q \sim \frac{1}{K_q(k(n))} q^{k(n)(n-k(n))}

wobei Kq=∏j=1∞(1−q−j)K_q = \prod_{j=1}^{\infty}(1-q^{-j}) die Euler-Funktion ist.

Technische Innovationen

1. Separate Behandlung gerader und ungerader Längen

Entdeckung, dass das asymptotische Verhalten für ungerade und gerade n wesentlich unterschiedlich ist und separate Behandlung erfordert:

  • Gerade Länge: Mit θ₃-Verteilung verbunden
  • Ungerade Länge: Mit θ₂-Verteilung verbunden

2. Präzise Analyse zentraler q-Binomialkoeffizienten

Beweis des asymptotischen Verhaltens zentraler q-Binomialkoeffizienten: (n⌊n/2⌋)q∼1Kqq⌊n/2⌋⌈n/2⌉\binom{n}{\lfloor n/2 \rfloor}_q \sim \frac{1}{K_q} q^{\lfloor n/2 \rfloor \lceil n/2 \rceil}

3. Konvergenz probabilistischer Verteilungen

Etablierung der Konvergenz diskreter Wahrscheinlichkeitsverteilungen zu kontinuierlichen Jacobi-θ-Verteilungen mit tiefgreifender probabilistischer Interpretation.

Experimentelle Einrichtung

Methoden zur theoretischen Verifikation

Da es sich um ein rein theoretisches Papier handelt, erfolgt die Verifikation der Ergebnisse hauptsächlich durch mathematische Beweise:

  1. Verifikation asymptotischer Analysen: Verifikation der Genauigkeit asymptotischer Formeln durch Kontrolle der Ordnung von Fehlertermen
  2. Überprüfung von Grenzfällen: Verifikation der Konsistenz der Formeln in Spezialfällen
  3. Vergleich mit bekannten Ergebnissen: Vergleich mit bestehenden Formeln für die Gesamtzahl der Äquivalenzklassen

Schlüsselbeispiele

Beispiel 3.1: k(n)=⌊n/2⌋−rk(n) = \lfloor n/2 \rfloor - r (r ist eine Konstante) Diese Funktionsklasse erfüllt Bedingung (⋆), da: k(n)(n−k(n))≥14n2−14−r2−rk(n)(n-k(n)) \geq \frac{1}{4}n^2 - \frac{1}{4} - r^2 - r

Beispiel 3.2: Allgemeinere Funktionsklassen k(n)=⌊n/2⌋−ℓ(n)k(n) = \lfloor n/2 \rfloor - \ell(n), wobei ℓ(n)∈o((εn−An)1/2)\ell(n) \in o((\varepsilon n - A\sqrt{n})^{1/2})

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

Satz 4.1 (Hauptergebnis)

Für k(n), das Bedingung (⋆) erfüllt, gilt wenn n → ∞:

Nk(n),nS∼qk(n)(n−k(n))Kqn!N^S_{k(n),n} \sim \frac{q^{k(n)(n-k(n))}}{K_q n!}

Nk(n),nM∼qk(n)(n−k(n))Kqn!(q−1)n−1N^M_{k(n),n} \sim \frac{q^{k(n)(n-k(n))}}{K_q n!(q-1)^{n-1}}

Nk(n),nΓ∼qk(n)(n−k(n))Kqhn!(q−1)n−1N^Γ_{k(n),n} \sim \frac{q^{k(n)(n-k(n))}}{K_q h n!(q-1)^{n-1}}

wobei h der Exponent in q = p^h ist.

Satz 5.1 (Asymptotisches Verhalten von Äquivalenzklassenverhältnissen)

Das asymptotische Verhalten der Äquivalenzklassenverhältnisse:

  • Gerade Länge: pe(k,m)∼KqKq(k)θ3(q−1)q−(m−k)2p_e(k,m) \sim \frac{K_q}{K_q(k)\theta_3(q^{-1})} q^{-(m-k)^2}
  • Ungerade Länge: po(k,m)∼KqKq(k)θ2(q−1)q−(m−k+1/2)2p_o(k,m) \sim \frac{K_q}{K_q(k)\theta_2(q^{-1})} q^{-(m-k+1/2)^2}

Korollar 5.3 (Beantwortung des offenen Problems)

S(2m)∼θ3(1/q)Kqqm2S(2m) \sim \frac{\theta_3(1/q)}{K_q} q^{m^2}S(2m+1)∼θ2(1/q)Kqq(m+1/2)2S(2m+1) \sim \frac{\theta_2(1/q)}{K_q} q^{(m+1/2)^2}

Dies löst vollständig das 2000 von Wild gestellte offene Problem über das exakte asymptotische Verhalten von S(n)S(n).

Wahrscheinlichkeitstheoretische Erkenntnisse

Korollar 5.2 (Verteilungskonvergenz)

Wenn m → ∞:

  • Pme→Pθ3P^e_m \to P_{\theta_3} (Konvergenz zur θ₃-Gaußverteilung)
  • Pmo→Pθ2P^o_m \to P_{\theta_2} (Konvergenz zur θ₂-Gaußverteilung)

wobei der Nome-Parameter 1/q ist.

Verwandte Arbeiten

Historische Entwicklung

  1. Wild (2000): Erste Untersuchung der asymptotischen Anzahl von Äquivalenzklassen binärer Codes, aber mit fehlerhaftem Beweis
  2. Lax (2004): Entdeckung und Aufzeigung von Problemen in Wilds Beweis
  3. Hou (2005-2009): Lieferung eines korrekten Beweisrahmens und Etablierung der asymptotischen Theorie für die Gesamtzahl der Äquivalenzklassen
  4. Dieses Papier: Erste systematische Untersuchung des dimensionsbeschränkten Falls und Etablierung tiefgreifender Verbindungen zur Wahrscheinlichkeitstheorie

Technischer Vergleich

  • Bestehende Methoden: Hauptsächlich Verwendung des Burnside-Lemmas und der Gruppenaktionstheorie
  • Innovationen dieses Papiers:
    • Einführung von Bedingung (⋆) zur präzisen Kontrolle des Wachstums der Dimensionsfunktion
    • Entdeckung wesentlicher Unterschiede zwischen geraden und ungeraden Längen
    • Etablierung der Verbindung zu Jacobi-θ-Funktionen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Vollständige Lösung des dimensionsbeschränkten Äquivalenzklassen-Zählproblems: Für Dimensionsfunktionen, die Bedingung (⋆) erfüllen, werden exakte asymptotische Formeln unter drei Äquivalenzrelationen gegeben
  2. Vereinheitlichung verschiedener Äquivalenzkonzepte: Beweis, dass die Äquivalenzklassenverhältnisse unter drei Äquivalenzrelationen dasselbe asymptotische Verhalten aufweisen
  3. Brückenschlag zwischen Codierungstheorie und Wahrscheinlichkeitstheorie: Entdeckung tiefgreifender Verbindungen zwischen der Äquivalenzklassenverteilung und diskreten Gaußverteilungen im Zusammenhang mit der Brownschen Bewegung
  4. Lösung eines wichtigen offenen Problems: Bereitstellung exakter asymptotischer Ausdrücke für die Summen von q-Binomialkoeffizienten

Einschränkungen

  1. Beschränkung der Dimensionsfunktionen: Bedingung (⋆) schließt einige wichtige Dimensionsfunktionen aus, wie konstante Dimension k(n) = α oder lineares Wachstum k(n) = λn (0 < λ < 1/2)
  2. Komplexität technischer Bedingungen: Die Form von Bedingung (⋆) ist relativ komplex und könnte den Anwendungsbereich der Ergebnisse einschränken
  3. Überlegungen zur praktischen Anwendung: Das Papier konzentriert sich hauptsächlich auf theoretische Ergebnisse, und die Orientierungsbedeutung für praktische Codierungsanwendungen erfordert weitere Forschung

Zukünftige Richtungen

  1. Erweiterung des Bereichs der Dimensionsfunktionen: Untersuchung der Anzahl von Äquivalenzklassen für Dimensionsfunktionen, die Bedingung (⋆) nicht erfüllen
  2. Berücksichtigung der Mindestdistanz: Einbeziehung von Mindestdistanz-Einschränkungen in das Äquivalenzklassen-Zählproblem
  3. Analyse der Rechenkomplexität: Untersuchung von Konstruktions- und Erkennungsalgorithmen für Äquivalenzklassen-Repräsentanten
  4. Anwendungsorientierte Forschung: Anwendung theoretischer Ergebnisse auf konkrete Codierungsdesignprobleme

Tiefgreifende Bewertung

Stärken

  1. Bedeutende theoretische Beiträge: Erste systematische Lösung eines wichtigen offenen Problems in der Codierungstheorie und Schließung einer theoretischen Lücke
  2. Ausgefeilte mathematische Techniken: Geschickte Anwendung von Gruppentheorie, Kombinatorik und asymptotischer Analyse mit strengem und vollständigem Beweis
  3. Interdisziplinärer Wert: Etablierung tiefgreifender Verbindungen zwischen Codierungstheorie und Wahrscheinlichkeitstheorie (insbesondere Brownsche Bewegungstheorie) mit wichtigem mathematischem Wert
  4. Vollständigkeit der Ergebnisse: Gleichzeitige Behandlung von drei Äquivalenzrelationen mit einheitlichem theoretischem Rahmen
  5. Lösung historischer Probleme: Beantwortung des 2000 von Wild gestellten offenen Problems über die Summen von q-Binomialkoeffizienten

Mängel

  1. Eingeschränkter Anwendungsbereich: Die Einschränkung durch Bedingung (⋆) macht es unmöglich, einige natürliche Dimensionsfunktionen (wie konstante Dimension) zu behandeln
  2. Unzureichende Praktikabilität: Als rein theoretische Forschung hat sie begrenzte direkte Orientierungsbedeutung für praktisches Codierungsdesign
  3. Rechenkomplexität: Obwohl asymptotische Formeln gegeben werden, ist die Berechnung für konkrete n-Werte immer noch komplex
  4. Verallgemeinerungsprobleme: Ergebnisse konzentrieren sich hauptsächlich auf lineare Codes, und die Verallgemeinerung auf nichtlineare Codes ist unklar

Einfluss

  1. Akademischer Einfluss: Wird voraussichtlich zu einer wichtigen Referenzliteratur in der asymptotischen Analyse der Codierungstheorie
  2. Theoretischer Wert: Eröffnet neue Richtungen für interdisziplinäre Forschung zwischen Codierungstheorie und anderen mathematischen Bereichen
  3. Methodologischer Beitrag: Die bereitgestellten Techniken könnten auf andere kombinatorische Zählprobleme mit Gruppenaktionsstruktur anwendbar sein

Anwendungsszenarien

  1. Theoretische Forschung: Forscher in den Bereichen Codierungstheorie, Kombinatorik und asymptotische Analyse
  2. Lehranwendung: Kann als Zusatzmaterial für fortgeschrittene Codierungstheorie-Kurse verwendet werden
  3. Verwandte Probleme: Andere kombinatorische Zählprobleme mit Gruppenaktionsstruktur

Literaturverzeichnis

Das Papier zitiert 18 wichtige Referenzen, hauptsächlich einschließlich:

  • Wild (2000): Bahnbrechendes Werk, das den grundlegenden Problemrahmen aufstellte
  • Hou (2005-2009): Systematische Etablierung der theoretischen Grundlagen der Äquivalenzklassen-Zählung
  • Huffman & Pless (2010): Standardlehrbuch der Codierungstheorie
  • Salminen & Vignat (2024): Wahrscheinlichkeitstheoretische Aspekte von Jacobi-θ-Funktionen

Dieses Papier stellt einen wichtigen Durchbruch in der asymptotischen Analyse der Codierungstheorie dar. Es löst nicht nur ein lange bestehendes theoretisches Problem, sondern etabliert auch tiefgreifende Verbindungen zur Wahrscheinlichkeitstheorie und hat wichtigen akademischen Wert und theoretische Bedeutung.