Linear representations of finite geometries and associated LDPC codes

Julien Sorci; Peter Sin; Qing Xiang

REVIEW 2 major objections 4 minor 14 references

Linear representations of finite geometries and associated LDPC codes

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that over any field in which $q$ is nonzero, the rank of a finite-geometry incidence matrix is $1+(q-1)h_K$, where $h_K$ is the number of hyperplanes meeting $K$, and that the resulting LDPC code is generated by its…

desk verdict Genuinely new rank formula and proof of Vandendriessche's conjecture, but the printed proof of Theorem 3.1 has a repairable gap in equation (11); this deserves a serious referee and conditional acceptance. read the letter →

arxiv 1908.06824 v2 pith:U2U3VAPX submitted 2019-08-19 math.CO

Peter Sin , Julien Sorci , Qing Xiang This is my paper · ORCID

classification math.CO MSC 05B2551E2094B05

keywords finitegeometrieslinearrepresentationsLDPCcodesincidencematrixrankplanewordscapacitorminimumdistancecharactertheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves a geometric formula for the rank of the point-line incidence matrix of a finite-geometry code: for a set $K$ of directions at infinity, over any coefficient field in which $q$ is nonzero, the rank equals $1 + (q-1)h_K$, where $h_K$ is the number of hyperplanes of the space at infinity that meet $K$. It uses this rank theorem to show that the low-density parity-check (LDPC) code whose parity-check matrix is the incidence matrix is generated by plane words, the words of minimum weight $2q$, settling a conjecture that had been proved only in the smallest dimension. The same character-theoretic machinery produces a generating set of capacitor words for the transposed code and lower bounds on its minimum distance, together with explicit rank formulas for special geometries such as the Wenger graph family and hyperovals. The interest is that purely geometric counts determine coding-theoretic parameters: dimension becomes a hyperplane intersection count, and minimum-weight codewords are visible as configurations of affine planes.

What carries the argument

The load-bearing object is the incidence map $\eta: F^L \to F^P$ sending each line to the sum of the characteristic functions of its $q$ points, viewed as a homomorphism of permutation modules for the additive group $V$ acting regularly on the affine points. The key identity is that the image of $\eta$ is spanned by the group characters $\lambda_\theta$ for which the corresponding $\mathbb{F}_q$-linear functional $\theta$ vanishes at some point of $K$; Lemma 2.2 shows that the nonroot characters of any translated line form a basis of the submodule it generates. The geometric translation is that nonzero $\theta$ define hyperplanes of the space at infinity $H$, and $q-1$ scalar multiples define the same hyperplane, yielding the count $1 + (q-1)h_K$. Plane words—differences of the sums of the $q$ affine lines through two distinct points at infinity inside an affine plane—are then shown, by induction on $|K|$ using a projection argument, to generate all of $C$.

What would settle it

Take $n=2$, $q=3$, and $K$ any two points of the four-point line at infinity; Theorem 1.1 predicts rank $5$ over any field of characteristic not $3$ ($1 + (3-1)\cdot 2$). Computing the rank of the $9\times 6$ point-line incidence matrix over, say, $\mathbb{F}_2$ and getting any value other than $5$ would refute the theorem. To probe the excluded case, compute the same rank over $\mathbb{F}_3$; a value strictly below $5$ would confirm that the $q=0$ restriction in Remark 1.2 is genuinely necessary.

Watch

Extended reading notes

Core claim

Let $H = \mathrm{PG}(V)$ be a hyperplane of $\mathrm{PG}(E)$, let $K$ be a subset of $H$, and let $N$ be the point-line incidence matrix of the affine space $P = \mathrm{PG}(E)\setminus H$ with lines whose direction lies in $K$. The paper's central result, Theorem 1.1, states that over any field $F$ with $q \neq 0$ the rank of $N$ is the number of linear functionals on $V$ that vanish on at least one point of $K$, equivalently $1 + (q-1)h_K$ with $h_K$ the number of hyperplanes of $H$ meeting $K$. The argument treats $F^P$ and $F^L$ as permutation modules for the additive group $V$ acting regularly on $P$; after adjoining a primitive $p$-th root of unity, the image of the incidence map is spanned by characters $\lambda_\theta$ whose associated functional $\theta$ has a zero in $K$, so rank reduces to counting such $\theta$. From this the paper derives Theorem 3.1: the code $C = \ker N$ is spanned by plane words, each of weight $2q$, so $C$ is generated by its minimum-weight words. For the transposed code $D = \ker N^T$ the paper shows capacitor words generate $D$ and that over totally ordered fields the minimum distance of $D$ is at least $2|K|$.

Load-bearing premise

The entire argument depends on $q$ being nonzero in the coefficient field $F$; when $q = 0$ in $F$ the rank formula is not claimed to hold and the paper gives no conjecture for that case.

Editorial extensions

If this is right

If $K$ contains a line of the hyperplane at infinity, $N$ has full rank $q^n$, so the corresponding LDPC code has the smallest possible dimension for its length.
For the Wenger graph family, the rank over any field with $q \neq 0$ equals the number of polynomials over $\mathbb{F}_q$ of degree at most $n-1$ that have a root in $\mathbb{F}_q$, giving an explicit dimension formula for the associated codes.
For $n=3$ and $K$ a hyperoval, the rank over fields of characteristic not 2 is $1 + (q-1)\binom{q+2}{2}$, and the formula is unchanged if one point is removed from $K$.
The minimum distance of the transposed code $D$ is at least $2|K|$ over any totally ordered field, with explicit codewords meeting this bound in small cases.
Whenever $C$ is nonzero, plane words have minimum weight $2q$ and generate $C$, so $C$ is generated by its minimum-weight codewords.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same character-theoretic reduction may apply to incidence systems built from higher-dimensional affine subspaces rather than lines, with the 'vanishing at a point of $K$' condition replaced by the condition that a functional vanish on an entire subspace meeting $K$; if so, the rank formulas would become counts of hyperplanes meeting $K$ in prescribed dimensions.
The paper leaves the $q = 0$ in $F$ case open; a natural program is to compute modular ranks for small $n$ and $K$ in characteristic dividing $q$ and look for a formula involving p-adic or modular representation data rather than plain hyperplane counts.
Because $C$ is generated by plane words, one could design decoding or syndrome-based algorithms that operate on the local affine-plane structure of minimum-weight configurations, not just on generic sparse parity checks.
The capacitor-word construction suggests that the true minimum distance of $D$ is governed by how the set $K$ sits relative to hyperplane arrangements in $H$; testing whether the $2|K|$ bound is tight for arbitrary $K$ would refine the paper's small examples.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Sin, Sorci and Xiang prove something genuinely new: a character-theoretic rank formula for the incidence matrix of any linear representation T*_{n−1}(K) over fields of characteristic not dividing q, and then use it to prove Vandendriessche's conjecture that the code C is generated by plane words. Theorem 1.1 is a clean unification of scattered cases (Wenger graphs, hyperovals, affine geometries), and the proof via Fourier analysis on the additive group is self-contained and convincing. Theorem 3.1 settles the conjecture for all n. The capacitor-word generating set for D (Theorem 3.3) is a nice additional result, and the applications to Wenger graphs and hyperovals give correct dimensions.

So the main ideas are sound and the paper is worth a careful referee. But the written proof of Theorem 3.1 contains a genuine error at the pivotal step. Equation (11) is false as printed. The middle equality drops the condition θ(u0)=0, and the last term uses the original incidence map η_K when the argument requires the incidence map of the quotient geometry T*_{n−2}(\bar K). This is not a missing symbol: the third equality is dimensionally wrong for the original η_K. A concrete check (n=2, q=3, K={u1}, u0=u2) gives 2 on the left, 6 for the printed middle term, and 0 for the printed final term. The repair is straightforward: replace the last η_K by the quotient map η_{\bar K}, which is exactly what the projection argument earlier in the proof produces. With that fix the induction closes.

Two smaller boundary defects: Theorem 1.1's geometric form 1+(q−1)h_K gives 1 when K=∅ but rank is 0, and Theorem 3.3's capacitor words do not generate D_K for K=∅ because the trivial character never appears in a capacitor word. Neither affects any nonempty K, but the statements should carry a K≠∅ hypothesis.

The citation pattern is honest; the self-citations are to cases the paper generalizes. The character theory is standard but applied cleanly. In short: the theorem is very likely correct, the present text is not. The authors should be asked to fix equation (11) and the K=∅ caveats before publication. This is exactly the kind of paper a serious editor should send to a knowledgeable referee rather than desk-reject.

Referee Report

2 major / 4 minor

Summary. The paper studies the point-line incidence system T^*_{n-1}(K) obtained from AG(n,q) by taking as lines all affine lines whose point at infinity lies in a subset K of the hyperplane at infinity. Its main result is a character-theoretic formula (Theorem 1.1) for the rank, over any field F with q nonzero, of the incidence matrix N, expressed as 1+(q−1)h_K, where h_K counts hyperplanes meeting K. From this it derives the dimension of the LDPC code C = ker N and, in Theorem 3.1, proves a conjecture of Vandendriessche that C is generated by plane words of weight 2q. The paper also studies the transpose code D = ker N^T, introduces capacitor words as generators, gives minimum-distance bounds and explicit examples, and applies the results to Wenger graphs and hyperovals.

Significance. If Theorem 3.1 is correct after the repairs noted below, the paper settles Vandendriessche's conjecture for all n and arbitrary K, a genuine advance in the theory of LDPC codes from finite geometries. The character-theoretic proof of Theorem 1.1 is elegant and self-contained, and it provides a uniform explanation of rank computations that were previously done case-by-case. The applications to Wenger graphs and hyperovals are concrete and useful. A clear strength is that the rank formula and the plane-word generation are derived from first principles rather than fitted to examples. The main limitation is the standing assumption q != 0 in F, which is explicitly acknowledged in Remark 1.2; the paper offers no result when q = 0 in F, so its scope is narrower than the most general coding-theoretic setting.

major comments (2)

[§3.1, Eq. (11)] The displayed chain of equalities in (11) is incorrect as printed. The second equality removes the condition θ(u0)=0, which is essential; for instance, for n=2, q=3, K={u1} and u0=u2, the first term equals 2 while the middle term equals 6. The third equality is also wrong: q^{n-1} − rank_F η_K uses the original incidence map η_K, whereas the intended count is q^{n-1} − rank_F η_{\bar K} for the quotient geometry T^*_{n-2}(\bar K). In the same example, q^{n-1} − rank_F η_K equals 0, while the left-hand side equals 2. Because this equation is precisely the induction step that proves C'=C, the proof of Theorem 3.1 is not valid as written. The argument appears repairable by tracking the quotient and invoking the induction hypothesis there, but the correction is substantive and must be made explicit.
[Theorem 1.1, statement] The geometric formula 1+(q−1)h_K is false for K=∅, since h_∅=0 but rank_F N=0 rather than 1. This boundary case is used in the induction of Theorem 3.1, where K=∅ is the base case and (11) with the intended correction relies on rank_F η_∅=0. The authors should either state Theorem 1.1 for nonempty K and treat the empty case separately, or add a convention that makes the formula correct for K=∅.

minor comments (4)

[Theorem 3.6] The proof should be expanded. The sentence 'Each such point t is also met by |K| lines, each of which contains a point u ... Therefore the sets ... both have cardinality at least |K|' does not by itself imply the lower bound on the positive support; a short double-counting argument between the positive and negative supports is needed to conclude that the positive support also has size at least |K|.
[Theorem 3.3] The proof applies Lemma 2.2 to conclude that a character appearing with nonzero coefficient in a capacitor word lies in W. This requires W to be an FV-submodule of F^P; this is true because the set of capacitor words is translation-invariant, but the fact is not stated and should be mentioned.
[Introduction, first paragraph] The name 'Gallagher' should be 'Gallager' to match reference [5].
[§3.1, after Eq. (11)] Once (11) is repaired, the image of K in the quotient should be denoted \bar K throughout to avoid confusion with the original set K.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the rank formula and plane-word theorem are derived from character theory and induction, not assumed or repackaged.

full rationale

The paper's derivation chain is self-contained. Theorem 1.1 is proved, not assumed: Lemmas 2.1 and 2.2 show that the image of the incidence map has an explicit F-basis consisting of the characters {λθ : ∃u∈K, θ(u)=0}, so rankF N is obtained by counting a basis; the geometric form 1+(q−1)h_K is a separate counting statement, not an input. No fitted parameter is renamed as a prediction. Theorem 3.1 is an induction that compares dimensions via Theorem 1.1; the conclusion C′=C follows from equality in a dimension inequality and is not inserted into the rank computation. The only self-citations, [10] and [13], refer to earlier special cases of LU(3,q) and are not load-bearing; the conjecture being proved is Vandendriessche's external conjecture [12]. The Wenger-graph and hyperoval applications are consequences of Theorem 1.1 rather than repackaged known results. Remark 1.2 explicitly limits the main theorem to fields with q≠0, which is an acknowledged scope condition, not an input-output equivalence. For the record, the displayed Equation (11) in the proof of Theorem 3.1 appears to contain a dropped hypothesis and a bar-notation slip; that is a correctness or erratum issue, not a circularity, and it does not affect this assessment.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters and no new postulated entities. It relies on standard character theory of finite abelian groups and standard affine and projective geometry facts; the only notable structural restriction is the assumption q nonzero in F, which is stated in the theorems.

assumptions (4)

standard math Rank of an integer matrix is invariant under extension of the base field.
Used at the start of Section 2 to justify replacing F by an extension containing a primitive p-th root of unity.
standard math Orthogonality relations for characters of finite abelian groups.
Used in Lemma 2.2 and in equation (2) to expand delta functions in the character basis.
standard math The characters of the additive group V are parametrized by the dual space V* via lambda_theta(v) equals omega to the Tr(theta(v)).
Gives the bijection between V* and the character group used throughout the proof of Theorem 1.1.
domain assumption Affine lines of P through a given point are determined by their point at infinity in H, and the group V acts regularly and transitively on P.
Structural property of affine space AG(n,q) underlying the definition of T*_{n-1}(K) and the module action.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Linear representations of finite geometries and associated LDPC codes." pith.science (2026). https://pith.science/paper/U2U3VAPX

@misc{pith2026190806824,
  author       = {Pith},
  title        = {Pith review of: Linear representations of finite geometries and associated LDPC codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U2U3VAPX}},
  note         = {Machine review of arXiv:1908.06824}
}

read the original abstract

The {\it linear representation} of a subset of a finite projective space is an incidence system of affine points and lines determined by the subset. In this paper we use character theory to show that the rank of the incidence matrix has a direct geometric interpretation in terms of certain hyperplanes. We consider the LDPC codes defined by taking the incidence matrix and its transpose as parity-check matrices, and in the former case prove a conjecture of Vandendriessche that the code is generated by words of minimum weight called plane words. In the latter case we compute the minimum weight in several cases and provide explicit constructions of minimum weight codewords.

Figures

Figures reproduced from arXiv: 1908.06824 by the authors.

**Figure 1.** A point a and two lines in the geometry T ∗ n−1 (K). lines in L, so that |L| = q n−1 |K|. A line in L will be viewed as a set of q points of P and we define a line to be incident to its points. This point-line incidence system is called the linear representation of the set K and is denoted by T ∗ n−1 (K) ( [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** The hyperplanes giving a capacitor word. infinity are both T. Define a d-capacitor word as the sum of the characteristic functions of points of S1 minus the corresponding sum of points of S2. It is easy to see that this is indeed a codeword of D of weight 2q d : given any line ℓ of L, either ℓ has no points contained in Y , or ℓ is totally contained in Y . In the latter case, ℓ must meet each of the hyperplanes S1 a… view at source ↗

**Figure 3.** The codewords w (left) and w ′ (right) of weights 6 and 8, respectively, given in Example 3.8. Remark 3.5. Part (4) of Lemma 3.4 implies that when K is properly contained in a line, either d(DK) ≥ 2|K| + 2 or DK has the same minimum distance as the code given by the parity-check matrix NT K restricted to the lines of T ∗ 1 (K). Theorem 3.6. Let F be a totally ordered field. Then the minimum distance of the F-code DK… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

P. Cara, S. Rottey, G. Van de Voorde, A construction for inﬁnite families of semisym- metric graphs revealing their full automorphism group , J. Alg. Combinatorics 39 (2014), 967-988. 15

work page 2014
[2]

P. Cara, S. Rottey, G. Van de Voorde, The isomorphism problem for linear representa- tions and their graphs , Advances in Geometry, 14 (2014), 353-367

work page 2014
[3]

Cioaba, F

S. Cioaba, F. Lazebnik, Weiqiang Li, On the spectrum of Wenger graphs , J. Combina- torial Theory B, 107 (2014), 132–139

work page 2014
[4]

De Clerck, H

F. De Clerck, H. Van Maldeghem, On linear representations of (α, β )-geometrie, Eur. J. Comb. 15, 311 (1994)

work page 1994
[5]

R. G. Gallager, Low-density parity-check codes, IRE Trans. Inform. Theory, vol. IT-18, pp.21-28, Jan. 1962

work page 1962
[6]

J. L. Kim, U. Peled, I. Perepelitsa, V. Pless and S. Friedland, Explicit construction of families of LDPC codes with no 4-cycles , IEEE Trans. Inform. Theory, 50 (2004), 2378-2388

work page 2004
[7]

Lazebnik and V

F. Lazebnik and V. Ustimenko, Explicit construction of graphs with arbitrary large girth and of large size , Discrete Appl. Math. 60 (1997), 275-284

work page 1997
[8]

S. E. Payne, J. A. Thas, Finite Generalized Quadrangles , (1985), Pitman, New York

work page 1985

Show all 14 references

[9]

V. Pepe, L. Storme, G. Van de Voorde, Small weight codewords in the LDPC codes arising from linear representations of geometries , J. Combin. Des. 17 (1) (2009), 1-24

2009
[10]

P. Sin, Q. Xiang, On the dimension of certain LDPC codes based on q-regular bipartite graphs, IEEE Trans. Inform. Theory 52 no. 8, (2006), 3735–3737

2006
[11]

H. Tang, J. Xu, Y. Kou, S. Lin, K. Abdel-Ghaﬀar, On Algebraic Construction of Gal- lager and Circulant Low-Density Parity-Check Codes , IEEE Trans. Inform. Theory 50 no. 6, (2004), 1269-1279

2004
[12]

Vandendriessche, LDPC codes associated with linear representations of geome tries, Advances in Mathematics of Communications 4 (3) (2010), 405–417

P. Vandendriessche, LDPC codes associated with linear representations of geome tries, Advances in Mathematics of Communications 4 (3) (2010), 405–417

2010
[13]

Vandendriessche, Some low-density parity-check codes derived from ﬁnite geo metries, Designs, Codes and Cryptography 54 (3) (2010), 287–297

P. Vandendriessche, Some low-density parity-check codes derived from ﬁnite geo metries, Designs, Codes and Cryptography 54 (3) (2010), 287–297

2010
[14]

Y. Kou, S. Lin, and M. P.C. Fossorier, Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results , IEEE Trans. Inform. Theory 47 no. 7, (2001), 2711-2736 Peter Sin, Department of Mathematics, University of Florid a, P. O. Box 118105, Gainesville ...

2001

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

P. Cara, S. Rottey, G. Van de Voorde, A construction for inﬁnite families of semisym- metric graphs revealing their full automorphism group , J. Alg. Combinatorics 39 (2014), 967-988. 15

work page 2014

[2] [2]

P. Cara, S. Rottey, G. Van de Voorde, The isomorphism problem for linear representa- tions and their graphs , Advances in Geometry, 14 (2014), 353-367

work page 2014

[3] [3]

Cioaba, F

S. Cioaba, F. Lazebnik, Weiqiang Li, On the spectrum of Wenger graphs , J. Combina- torial Theory B, 107 (2014), 132–139

work page 2014

[4] [4]

De Clerck, H

F. De Clerck, H. Van Maldeghem, On linear representations of (α, β )-geometrie, Eur. J. Comb. 15, 311 (1994)

work page 1994

[5] [5]

R. G. Gallager, Low-density parity-check codes, IRE Trans. Inform. Theory, vol. IT-18, pp.21-28, Jan. 1962

work page 1962

[6] [6]

J. L. Kim, U. Peled, I. Perepelitsa, V. Pless and S. Friedland, Explicit construction of families of LDPC codes with no 4-cycles , IEEE Trans. Inform. Theory, 50 (2004), 2378-2388

work page 2004

[7] [7]

Lazebnik and V

F. Lazebnik and V. Ustimenko, Explicit construction of graphs with arbitrary large girth and of large size , Discrete Appl. Math. 60 (1997), 275-284

work page 1997

[8] [8]

S. E. Payne, J. A. Thas, Finite Generalized Quadrangles , (1985), Pitman, New York

work page 1985