Preprint · complete, not yet posted or submitted

Weighted Fourier certificates for maximum nullity in generalized Petersen graphs: rational classification and arithmetic obstructions

Mohib Ahmad · Independent Researcher · ORCID 0009-0001-8170-8179

Download PDF · 13 pages Verification code

Status, stated plainly

Finalized 2026-08-31 and packaged for arXiv (math.CO) and Linear Algebra and its Applications. It has not been posted to arXiv, submitted to a journal, peer-reviewed, or accepted anywhere, and it carries no DOI or arXiv identifier. The author’s ORCID record registers no works. Every internal check it makes of itself passes; none of that is peer review, and this page does not present it as such.

Abstract

For a graph G, the maximum nullity M(G) of the real symmetric matrices described by G satisfies M(G) ≤ Z(G), where Z(G) is the zero forcing number. Alameda et al. proved Z(P(n,k)) ≤ 2k+2 for generalized Petersen graphs, and Krishnan recently corrected the published claim for P(n,3) by showing Z(P(12,3)) = 7 and conjecturing Z(P(n,3)) = 8 for every n ≥ 13. We construct weighted block-circulant matrices in S(P(n,k)) and diagonalize them by the discrete Fourier transform. For P(n,3) the singularity condition is encoded by an eighth-degree reciprocal polynomial. Explicit root-of-unity certificates prove M(P(n,3)) = Z(P(n,3)) = 8 whenever 10, 24, 28 or 42 divides n; these indices have natural density 1/6. We then determine the rational part of this construction completely, and derive arithmetic obstructions from the Lam–Leung theorem on vanishing sums of roots of unity.

MSC 2020: Primary 05C50; Secondary 15A03, 15A18, 11R18
Keywords: zero forcing numbermaximum nullitygeneralized Petersen graphblock-circulant matrixFourier diagonalizationcyclotomic polynomialvanishing sums of roots of unity

What it proves

Four results. The third and fourth are the ones worth reading twice — one bounds the method itself, and the other generalizes it.

01
M(P(n,3)) = Z(P(n,3)) = 8 when 10, 24, 28 or 42 divides n
Explicit root-of-unity certificates, covering a set of indices of natural density 1/6. This settles Krishnan's conjecture on that set.
02
The rational part of the construction is classified completely
If the three weight parameters are rational and all eight roots are distinct roots of unity, exactly six parameter triples occur, with minimal moduli 10, 24, 40 and 42. The modulus-28 certificate is therefore genuinely algebraic rather than rational.
03
A Lam–Leung obstruction bounds the whole certificate class
Any certificate at level n forces 27 into the numerical semigroup generated by the prime divisors of n. Consequently no admissible prime level supports a constant-weight certificate, and among levels n = 2p with p an odd prime only n = 10 occurs.
04
A signed construction extends the result to general step size
If Q_k(z) = z^(2k+2) + z^(2k) + z^(k+1) + z^2 + 1 divides z^L − 1, then M(P(Lr,k)) = Z(P(Lr,k)) = 2k+2 for every r ≥ 1. In particular M(P(120r,7)) = Z(P(120r,7)) = 16.

The four families

The result holds whenever n is divisible by one of these four numbers, and together they have natural density 1/6. Each mark below is that modulus's roots of unity, with the certificate's eight roots picked out where they actually sit.

n ≡ 0 (mod 10)

Φ₅·Φ₁₀

the smallest certificate

n ≡ 0 (mod 24)

Φ₃·Φ₆·Φ₈

three cyclotomic factors, not two

n ≡ 0 (mod 28)

algebraic — no rational factorization

algebraic, not rational

n ≡ 0 (mod 42)

Φ₃·Φ₁₄

two distinct certificates

The four are not interchangeable. 10 is the smallest and its certificate is every tenth root of unity except z = ±1. 24 needs three cyclotomic factors rather than two. 28 has no rational factorization at all — its certificate is genuinely algebraic, which is why its mark has nothing picked out. And 42 carries two distinct certificates, Φ₃·Φ₁₄ and Φ₆·Φ₇.

The rational certificates

Fourteen degree-8 products of distinct cyclotomic polynomials were enumerated. Eight are degenerate. These six are what remain — the complete rational part of the construction.

The six valid rational certificates, with weight parameters and minimal modulus
Cyclotomic factors	p	q	τ	Minimal modulus L
Φ₅·Φ₁₀	0	0	-1	10
Φ₃·Φ₆·Φ₈	0	0	-2	24
Φ₅·Φ₈	1	1	-1	40rational, not covered
Φ₈·Φ₁₀	-1	-1	-1	40rational, not covered
Φ₃·Φ₁₄	0	-1	-1	42
Φ₆·Φ₇	0	1	-1	42

The rational moduli are 10, 24, 40, 42, but the result is proved on 10, 24, 28, 42. The two lists differ in both directions, and each difference is a fact about the construction: 40 admits a rational certificate that adds no new covered indices, since every multiple of 40 is already a multiple of 10; and 28 is covered by a certificate that is not rational at all.

Computed independently

Zero forcing numbers for P(n,3), from the exhaustive search in the supplement. It reproduces Krishnan's boundary counterexample rather than assuming it.

n = 76

n = 86

n = 96

n = 108

n = 117

n = 127

n = 138

n = 148

n = 158

n = 168

n = 178

n = 188

n = 198

n = 208

Z(P(12,3)) = 7 is the counterexample that broke the previously published claim, and it falls out of this computation independently. Values continue at 8 through n = 27.

Checks that ship with the paper

Symbolic checks: 18 / 18 pass; verify_paper.py
Rational classification: 14 candidates → 6 valid; classify_rational.py
Exhaustive search: no new modulus ≤ 420; search_moduli.py
Zero forcing, exact: 7 ≤ n ≤ 27; zero_forcing.c

What it does not settle

The paper is explicit about the boundary of its own method, which is the less common half of a result.

The certificate class cannot by itself settle the conjecture for all n ≥ 13. The paper proves this rather than leaving it open.
The computer-assisted search up to modulus 420 is reported as computational evidence, not a nonexistence proof.
The uniform lower bound Z(P(n,3)) ≥ 8 remains open outside the covered families.

Open engineering questions

Separate from the mathematics. Each of these is grounded in a project in this repository, so it can be traced to code rather than taken on trust.

Rules as code, and the limits of model-assisted extraction

How much of the translation from published regulation to executable logic can a language model do, if it is never allowed to decide anything?

Built a compiler where the model only ever proposes candidates, six deterministic checks stand between it and the IR, every semantic object carries a source span back to the authoritative text, and no rule executes until a human approves it. Then tried to break the review gate on purpose with seeded errors.

Typed IR with a closed expression ASTFour-state deterministic evaluationMutation testingAdversarial review gate

RuleWeaver

Clinical operations, evidence versus prediction

Is a denial-risk probability the wrong output for a prior-authorization workflow, and is criterion-level evidence the right one?

Started with a denial-prediction prototype, then rejected that framing. The current architecture will not let a denial probability sort a work queue or feed a gate; what it produces instead is criterion-level provenance against versioned policy, moving through one canonical state machine.

Criterion DSLFive-value status algebraVersioned policyDeterminism boundary

Priora

Concurrent systems and observability

What is the minimum telemetry needed to see queue pressure and ordering faults in a streaming pipeline, without coupling observability to packet processing?

Implemented a three-stage pipeline over bounded multiprocessing queues with signature verification and packet re-sequencing, exposing state through an observer rather than reaching into the workers.

Bounded queuesMultiprocessingObserver patternPacket re-sequencing

StreamScope