Skip to content
Mohib Ahmad

Preprint · complete, not yet posted or submitted

Weighted certificates over real and finite fields for generalized Petersen graphs

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

Download PDF · 19 pages Verification code

Status, stated plainly

Finalized 2026-09-08 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

We study the corrected conjecture Z(P(n,3))=8 for n≥ 13 using weighted graph-pattern matrices. Over the reals, Fourier certificates prove M(P(n,3))=Z(P(n,3))=8 whenever 10, 24, 28, or 42 divides n. We retain the complete six-triple rational classification and strengthen the arithmetic obstruction: no prime-power level supports nullity eight in the real constant-weight symmetric class. An exact modular sieve followed by cyclotomic verification gives a complete classification through level 420. Changing the coefficient field yields additional zero-forcing families. A polynomial greatest-common-divisor formula computes the nullity of a five-parameter cyclic matrix over any field, including when the characteristic divides the graph order. Explicit finite-field certificates prove Z(P(Lr,3))=8 for all r≥ 1 and L in {16,17,18,19,21,22,23,25,26,27,29,31}. In particular, a binary degree-eight divisor of z^17−1 proves Z(P(17r,3))=8. These certificates do not assert real maximum nullity eight. For the signed real specialization, we determine every root-of-unity zero and prove that Q_k(z)=z^(2k+2)+z^(2k)+z^(k+1)+z^2+1 is squarefree cyclotomic exactly when k=2,3,7. Finally, a first-force anchoring lemma reduces exhaustive seven-vertex zero-forcing search to O(n^4) candidate sets and verifies the conjecture for every 13≤ n≤ 64. The uniform conjecture remains open.

MSC 2020
Primary 05C50; Secondary 15A03, 15A18, 11R18
Keywords
zero forcing numbermaximum nullitygeneralized Petersen graphgraph-pattern matrixblock-circulant matrixFourier diagonalizationfinite fieldscyclotomic polynomial

What it proves

Seven results. Two are worth reading twice, and both are about the boundary of the method rather than its reach — one bounds the real construction, the other says plainly what changing the field does not buy.

  1. 01

    M(P(n,3)) = Z(P(n,3)) = 8 when 10, 24, 28 or 42 divides n

    Explicit root-of-unity certificates over the reals, covering a set of indices of natural density 1/6. This settles Krishnan’s conjecture on that set, and it is the only result here that reaches maximum nullity.

  2. 02

    Over finite fields, Z(P(Lr,3)) = 8 for twelve further base levels

    A greatest-common-divisor formula gives the nullity of the five-parameter cyclic matrix over any field, including when the characteristic divides the graph order. Certificates follow for L in 16, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 31 and every multiple. A binary degree-eight divisor of z¹⁷ − 1 handles L = 17.

  3. 03

    The two families together cover 46.31% of all indices

    Natural density 6933083/14969435 by inclusion–exclusion over the fifteen base levels, after dropping 42 as a multiple of 21. On this union the zero forcing number is 8; on the real sixth of it, the maximum nullity is 8 as well.

  4. 04

    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.

  5. 05

    A Lam–Leung obstruction bounds the whole real certificate class

    Any certificate at level n forces 27 into the numerical semigroup generated by the prime divisors of n. No prime-power level supports nullity eight in the real constant-weight symmetric class, and an exact modular sieve with cyclotomic verification classifies every level through 420.

  6. 06

    The signed construction is squarefree cyclotomic exactly for k = 2, 3, 7

    Every root-of-unity zero of Q_k(z) = z^(2k+2) + z^(2k) + z^(k+1) + z² + 1 is determined, and those three values of k are the only ones. For k = 7 this gives M(P(120r,7)) = Z(P(120r,7)) = 16.

  7. 07

    Exhaustive search verifies the conjecture for every 13 ≤ n ≤ 64

    A first-force anchoring lemma cuts the seven-vertex search to O(n⁴) candidate sets. No seven-vertex forcing set exists in that range, and eight consecutive outer vertices force in every case tested.

The four families

Over the reals the result holds whenever n is divisible by one of these four numbers, and together they have natural density 1/6. These are the families where both maximum nullity and zero forcing are settled. 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 factorspqτMinimal modulus L
Φ₅·Φ₁₀00-110
Φ₃·Φ₆·Φ₈00-224
Φ₅·Φ₈11-140rational, not covered
Φ₈·Φ₁₀-1-1-140rational, not covered
Φ₃·Φ₁₄0-1-142
Φ₆·Φ₇01-142

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.

Changing the field

The revision drops the requirement that the matrix entries be real. Over a finite field the same construction reaches twelve further base levels — at a price, stated below rather than buried.

  • L = 16char 17
  • L = 17char 2inseparable
  • L = 18char 19
  • L = 19char 229
  • L = 21char 41
  • L = 22char 23
  • L = 23char 461
  • L = 25char 499
  • L = 26char 5inseparable
  • L = 27char 271
  • L = 29char 233
  • L = 31char 743

Each level certifies every multiple, so Z(P(Lr,3)) = 8 for all r ≥ 1. The two marked rows are the cases where the characteristic divides the graph order — exactly the situation the ordinary Fourier argument cannot reach, and the reason the nullity is computed by a polynomial gcd that is stated for any field. L = 17 is the neatest of them: a degree-eight divisor of z¹⁷ − 1 over 𝔽₂.

What each field buys

Real certificates
16.67% · M = Z = 8
density 1/6
Union with finite fields
46.31% · Z = 8
density 6933083/14969435

The wider families settle the zero forcing number, not the maximum nullity. Reduction modulo a prime can lower rank, so a finite-field kernel need not lift to a real one. The paper states this itself and this page does not round it away.

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. The original program continues at 8 through n = 27. The revision adds a first-force anchoring lemma that cuts the seven-vertex search to O(n⁴) candidate sets, and with it the range runs unbroken to n = 64 with no seven-vertex forcing set anywhere in it.

Checks that ship with the paper

Symbolic checks
18 / 18 pass
verify_paper.py
Original proofs retained
17 / 17 verbatim
integration_validation.json
Rational classification
14 candidates → 6 valid
classify_rational.py
Exact sieve
complete through level 420
exact_search.py
Finite-field certificates
12 levels, ranks confirmed
verify_finite_fields.py
Zero forcing, exhaustive
13 ≤ n ≤ 64, no 7-set
direct_zf_anchor.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 finite-field certificates prove the zero forcing number only. Reduction modulo a prime can lower rank, so a finite-field kernel need not lift to a real one, and maximum nullity is not claimed on those families.
  • The real certificate class cannot by itself settle the conjecture for all n ≥ 13. The paper proves this rather than leaving it open.
  • The exhaustive computation establishes the range 13 ≤ n ≤ 64 and nothing beyond it. The uniform conjecture Z(P(n,3)) = 8 for every n ≥ 13 remains open.
  • The paper does not establish priority over all existing literature, and no part of it has been peer-reviewed.

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