Source-linked AI summary
A $G$-Invariant Erd\H{o}s--Hanani Theorem with Applications to Optical Orthogonal and Constant-Weight Codes
Yeow Meng Chee
TL;DR
The paper asks whether the Johnson bound can be asymptotically attained at every length for constant-weight optical orthogonal codes, beyond families known for particular parameters or lengths. It uses hypergraph matchings to construct group-invariant packings and establishes all-length attainment for several code families, along with an asymptotic maximum for a two-dimensional case.
Problem
Whether the Johnson bound is asymptotically attained at every length for OOCs with constant w and λ remained open, while known asymptotically optimal families covered particular parameters or length forms.
Source: §1 · p. 2Method
The proof selects orbits in a hypergraph matching whose vertices are eligible t-subset orbits and whose edges arise from k-subset orbits.
Source: §1 · p. 3Results
At all lengths, the Johnson bound is asymptotically attained by OOCs and their multidimensional and signature-pattern versions for constant w and λ with w ≥ λ + 2; the method also determines the asymptotic maximum for two-dimensional OOCs with at most one pulse per wavelength.
Source: §1 · p. 3Takeaways & Limitations
Semiregular groups satisfy the required stabilizer condition automatically for t ≥ 3, while for t = 2 it depends on the number of involutions.
Source: §1 · p. 3Whether the β_k,t(G) hypothesis in Theorem 3 is necessary remains open; equivalently, it is open whether α_k,t(G) → 0 alone suffices.
Source: §6 · p. 15
Abstract
from arXiv · showhide
Let $k>t\ge 2$ be fixed integers, and let $G$ be a permutation group on a set of $v$ points. A $G$-invariant packing is free if every block has $|G|$ distinct images under $G$. We give two conditions on $G$ under which, as $v\to\infty$, there is a free $G$-invariant $t$-$(v,k,1)$ packing with $(1-o(1))\binom{v}{t}/\binom{k}{t}$ blocks. This is a $G$-invariant form of the Erd\H{o}s--Hanani theorem on asymptotically optimal packings. For semiregular groups $G$, packings with these properties exist if and only if all but $o(v^t)$ of the $t$-subsets of points have trivial setwise stabiliser. This property is satisfied by every semiregular group for $t\ge 3$, and by every cyclic semiregular group for $t=2$. As a consequence, the Johnson bound is asymptotically attained at all lengths by optical orthogonal codes of constant weight $w$ and constant correlation $\lambda$ with $w\ge\lambda+2$, by their multidimensional and signature pattern versions, and by cyclic and quasi-cyclic constant-weight codes. The same method gives a form of the theorem for group divisible packings that are invariant under a cyclic group. This determines the asymptotic maximum size of two-dimensional optical orthogonal codes with at most one pulse per wavelength.
1 Introduction
The introduction asks when asymptotically optimal packings can be required to respect a prescribed group, and applies the answer to optical and constant-weight codes. It also extends the approach to cyclically invariant group-divisible packings.
1 Introduction
- Whether the Johnson bound is asymptotically attained at every length for constant w and λ had remained open, despite results for particular parameters and length families.The ordinary Erdős–Hanani asymptotic packing theorem did not provide packings invariant under a prescribed group.Source: §1 · p. 2
- For cyclic OOCs, codeword supports and their translates form a free Z_v-invariant (λ + 1)-(v,w,1) packing, making asymptotic Johnson-bound attainment equivalent to asymptotically optimal packings.The packing has v|C| blocks when the code has |C| codewords.Source: §1 · p. 2
- For constant w and λ with w ≥ λ + 2, the Johnson bound is asymptotically attained at all lengths by OOCs and their multidimensional and signature-pattern versions.Cyclic and quasi-cyclic constant-weight binary codes also asymptotically attain the maximum size for constant w and 2 ≤ δ ≤ w − 1.Source: §1 · p. 3
- For semiregular G, asymptotically optimal free G-invariant packings exist if and only if ν_t(G) = o(v^t); this holds for every such group when t ≥ 3.For t = 2, ν_2(G) = ι(G)v/2, so the condition is ι(G) = o(v), where ι(G) counts involutions.Source: §1 · pp. 2–3
- The proof selects orbits through a hypergraph matching, with one obstacle being to show that almost all k-subsets yield edges and another being to bound codegrees.The general theorem measures these obstacles with α_k,t(G) and β_k,t(G); for semiregular groups, β_k,t(G) = O(1/v) and α_k,t(G) = O(1/v + ν_t(G)/v^t).Source: §1 · p. 3
- The method also gives cyclically invariant group-divisible packings that determine the asymptotic maximum size of two-dimensional OOCs with at most one pulse per wavelength.These packings use transversal k-subsets, with Z_T acting by translation of the second coordinate.Source: §1 · p. 3
2 Group Actions and Main Results
For semiregular groups, asymptotically optimal free invariant packings are characterized by how many t-subsets have nontrivial stabilizers. The paper quantifies that obstruction and identifies when it is negligible.
2 Group Actions and Main Results
- A free invariant packing is a union of group orbits of blocks, with each free block having |G| distinct images.A subset is free when its stabilizer is trivial; P_G(v,k,t) denotes the maximum number of blocks in such a packing.Source: §2 · p. 3
- For semiregular groups, ν_2(G) = ι(G)v/2, while ν_t(G) ≤ v^(t−1) for t ≥ 3.Thus the obstruction is automatically negligible for t ≥ 3; for t = 2 it requires ι(G) = o(v).Source: §2 · pp. 4–5
- A sequence of semiregular groups admits asymptotically optimal free invariant packings if and only if ν_t(G) = o(v^t).Here ν_t(G) counts t-subsets fixed setwise by some nonidentity group element.Source: §2 · p. 5
- For G = Z_2^a acting by translation, every 2-subset is stabilized by a translation, and every invariant 2-(v,k,1) packing is empty for k ≥ 2.For odd k ≥ 3, any invariant packing is free, so the stated emptiness follows from the obstruction bound.Source: §2 · p. 5
3 Orbit Hypergraphs
The proof converts invariant packings into matchings in an orbit hypergraph. Bounds on vertex degrees and codegrees then provide large matchings, while semiregularity controls the relevant error parameters.
3 Orbit Hypergraphs
- The construction uses t-separated blocks: no nonidentity image of a block may overlap it in t or more points.This condition ensures that the block and its t-subsets are free, and that each t-subset occurs in only one translate within the orbit.Source: §3 · p. 6
- A matching in the orbit hypergraph yields a free invariant packing, with m|M| blocks for a matching M.Each edge represents an orbit of t-separated k-subsets, and its vertices are the orbits of the t-subsets contained in a representative block.Source: §3 · p. 6
- If every vertex has degree at most D and distinct vertices have codegree at most δD, the matching argument yields at least |F|/((1 + ε)D) blocks from F.The Kahn matching theorem supplies at least |F|/((1 + ε)mD) edges; each matched edge contributes m blocks.Source: §3 · pp. 5–7
- For semiregular G, β_k,t(G) ≤ (t²k + k^t)/v: intersecting images contribute at most t²k/v and disjoint images at most k^t/v, so β_k,t(G) = O(1/v) for fixed k,t.Source: §3 · p. 8
4 Proofs of the Main Results
The proof combines an upper bound that excludes nonfree t-subsets with a matching-based lower bound from t-separated blocks. Semiregularity makes the lower-bound error terms small under the stated stabilizer condition.
4 Proofs of the Main Results
- A free packing can cover only t-subsets with trivial stabilizer, giving an upper bound from the number of free t-subsets.A nonfree t-subset in a block would also lie in a distinct image of that block, contradicting the packing property.Source: §4 · p. 8
- The lower-bound argument takes the family of t-separated k-subsets and applies the general theorem to obtain a large free invariant packing.The proof estimates the size of that family using α_k,t(G), then invokes the theorem under its β_k,t(G) hypothesis.Source: §4 · p. 8
- For semiregular groups, the proof bounds β_k,t(G) by c_1/v and α_k,t(G) by c_1/v + c_1ν_t(G)/v^t.These estimates make the general invariant Erdős–Hanani theorem applicable when ν_t(G) is negligible compared with v^t.Source: §4 · pp. 8–9
5 Applications
The applications connect invariant packings to asymptotic Johnson-bound attainment across optical and constant-weight code families. They also extend the approach to cyclically invariant group divisible packings and optical codes with at most one pulse per wavelength.
5 Applications
- For semiregular groups with at most three involutions, the applications determine the asymptotic maximum size of the associated invariant codes.The code families include OOCs, multidimensional OOCs, optical orthogonal signature pattern codes, and quasi-cyclic constant-weight codes.Source: §5 · p. 9
5.1 Optical Orthogonal Codes
- Multidimensional OOC bounds are asymptotically tight uniformly in dimension and coordinate sizes.The application also identifies optical orthogonal signature pattern codes with invariant packings under a product of cyclic groups.Source: §5.1 · p. 11
- For families on an arbitrary group A, the asymptotic maximum is attained when λ ≥ 2 and w ≥ λ + 2.For λ = 1 and w ≥ 3, attainment holds if and only if A has o(v) involutions; for λ = 1 and w ≥ 2, elementary abelian 2-groups admit no nonempty such family.Source: §5.1 · p. 11
5.2 Cyclic and Quasi-Cyclic Constant-Weight Codes
- Cyclic and quasi-cyclic constant-weight codes with full shift orbits are equivalent to free invariant packings, yielding the asymptotic code-size result.The result applies for every n and divisor ℓ of n.Source: §5.2 · p. 12
- Quasi-cyclic constant-weight codes attain the unrestricted asymptotic maximum uniformly over all divisors ℓ of n.The result covers all w, 2 ≤ δ ≤ w−1, and lengths n.Source: §5.2 · p. 12
5.3 Group Divisible Packings and OOCs with at Most One Pulse per Wavelength
- Cyclically invariant group divisible packings give the asymptotic maximum size of two-dimensional OOCs with at most one pulse per wavelength.The correspondence identifies the code maximum with the invariant-packing maximum divided by T; the result applies for all λ ≥ 1 and w ≥ λ + 2, without a condition on T.Source: §5.3 · p. 14
6 Concluding Remarks
For semiregular groups, the bound is asymptotically attained when the number of t-subsets with nontrivial setwise stabiliser is o(v^t). The dihedral action on Z_v also yields asymptotically optimal free packings for t≥3, but not for t=2.
6 Concluding Remarks
- For semiregular G, Theorem 4 gives asymptotic equality in (4) when ν_t(G) = o(v^t).The existence of Steiner systems with a prescribed semiregular automorphism group remains open in general.Source: §6 · p. 14
- The existence of Steiner systems with a prescribed semiregular group of automorphisms is open in general.Source: §6 · p. 14
- For the dihedral group acting on Z_v, α_k,t(G) = O(1/v) when t≥3, yielding asymptotically optimal free invariant packings.The argument bounds β_k,t(G) by (2t^2k + 2kt)/v.Source: §6 · pp. 14–15
- For t=2, every 2-subset {x,y} of Z_v is mapped to itself by reflection z↦x+y−z; also, P_G(v,k,2) = 0 by Proposition 2.Source: §6 · p. 15
- Whether Theorem 3's hypothesis on β_k,t(G) is necessary remains open; equivalently, it is unknown whether α_k,t(G) → 0 alone suffices for asymptotic equality.Source: §6 · p. 15