Maximum distinct character values in finite projective systems
Extremal character spectra of finite projective systems
Information Theory
Summary
This paper studies how to maximize the variety of values a certain function takes when applied to collections of points in a finite projective space, which is a mathematical setting used in coding theory and combinatorics. The authors find the largest number of distinct values possible under certain size and multiplicity constraints, and fully solve the problem in a key special case. They also provide new mathematical inequalities that describe the structure of these value patterns. These findings relate to the properties of specific error-correcting codes called subcodes.
What this means in practice
- •For coding theory engineers: Design error-correcting codes with optimized distinct weight patterns for subcodes, improving code analysis and performance guarantees.
- •For combinatorial optimization teams: Utilize character spectrum bounds to inform designs of combinatorial structures under size and multiplicity constraints.
A theory result. No direct application yet.
Authors
Shitao Li, Yang Li, Gaojun Luo
Abstract
Let $\mathcal M$ be a finite spanning multiset of points in ${\rm PG}(k-1,q)$, and let ${\rm Char}_{\mathcal M}$ be its character function. For $1\le r\le k$, we study the maximum number of distinct values attained by ${\rm Char}_{\mathcal M}$ on the codimension-$r$ flats under a total-multiplicity budget. The spectrum is subject to two natural upper bounds, whose extremal cases lead respectively to $r$-maximum character spectrum ($r$-MCS) and $r$-full character spectrum ($r$-FCS) systems. We establish the existence of $r$-FCS systems in a broad parameter range, and solve the size-constrained extremal problem completely when $r=k-1$, including the minimum-cost multiplicity profiles. For $1\le r<k$, put $M_r=\qbinom{k}{r}$ and $B_r=\qbinom{k-1}{r}$. The minimum size $ν_r(k,q)$ of an $r$-MCS system satisfies \[\left\lceil\frac{\binom{M_r}{2}}{B_r}\right\rceil\le ν_r(k,q)\le \binom{M_r-1}{2}+\frac{q^k-q^{k-r}}{q-1}.\] The upper bound is at most $\binom{M_r}{2}$, strictly less when $r\le k-2$, and exact when $r=k-1$. Its proof applies positive additive labelings to the complement of one flat, whose trace is empty while all remaining traces are distinct. For $r=1$, we improve the known upper bounds on the minimum length of such systems. We also develop global moment identities and local flat-incidence bounds that impose strong structural constraints on large character spectra. Under the projective-system correspondence, complementary character spectra are the support-weight spectra of $r$-dimensional subcodes.