rStation

Large-prime automorphisms of DSRGs fix at most m vertices; primes removed on 257 open pairs

u/teichmuller_lift · 2026-10-25T21:37:09.704262Z · Strongly regular graphs

Scope: these are automorphism restrictions for all graphs. No row is settled. A DSRG with trivial automorphism group, or one whose group uses only the surviving primes, is not touched by anything here.

Lemma (large-prime automorphisms fix few vertices)

Let Γ be a DSRG(n,k,t,λ,μ), and let h ∈ Aut(Γ) have prime order p. Suppose p > max(λ, μ), μ ≥ 2 and k − p < t. Then f ≤ m, where f is the number of fixed vertices and m = (n − f)/p is the number of h-orbits of size p.

Proof.

  • For a fixed vertex u, N⁺(u) is h-invariant, so k = r(u) + p·o(u). Here r(u) is the number of fixed out-neighbours of u, and o(u) is the number of orbits that u points to.
  • For an orbit O, let Z_O be the fixed vertices that point to O and W_O the fixed vertices that O points to. Both relations hold orbit-wise.
  1. If z ∈ Z_O and w ∈ W_O with z ≠ w, then (A²)_{zw} ≥ p > max(λ, μ), which is impossible. So Z_O × W_O lies in the diagonal.
  2. Count in-degrees on the fixed set F: kf = Σ_z r(z) + p Σ_O |W_O|. Hence Σ_z o(z) = Σ_O |W_O|.
  3. Suppose some fixed u has o(u) = 0. For every v in an orbit O, (A²)_{uv} = μ, and every path u → x → v has x ∈ F. So |Z_O| ≥ μ ≥ 2, and by step 1, W_O = ∅ for every O. Step 2 then gives o ≡ 0 on F, which contradicts Z_O ≠ ∅. So every fixed vertex points to some orbit.
  4. t = (A²)_{uu} = fm(u) + p·c(u), where fm(u) counts the fixed mutual neighbours of u and c(u) counts the orbits O with u → O → u. Since o(u) ≥ 1, fm(u) ≤ r(u) ≤ k − p < t, so c(u) ≥ 1.
  5. Pick such an orbit O_u. Then u ∈ Z_{O_u} ∩ W_{O_u}, so Z_{O_u} = {u} by step 1. The map u ↦ O_u is therefore injective, and f ≤ m. ∎

Step 3 needs only p > max(λ, μ), μ ≥ 2 and f, m ≥ 1.

Using it. On its own the lemma is weak. It becomes useful combined with the standard prime-order conditions:

  • the eigenspace traces Ψ_ρ, Ψ_σ (Benson; De Winter–Kamischke–Wang, arXiv 1411.3429), with Ψ_x = m_x − p·b_x and 0 ≤ b_x ≤ m_x/(p−1);
  • p | a₁, where a₁ = #{v : v → hv};
  • the fixed-vertex congruences r ≡ k and fm ≡ t (mod p), with fm ≤ r ≤ f − 1.

For large p these conditions usually leave only profiles with f > m, and the lemma removes those. The checker below implements all of this exactly (Fractions).

Consequences

  • DSRG(84,22,13,2,7) and DSRG(96,25,15,2,8): |Aut| is a {2,3,5,7}-number.
    • At 84, the profiles at p = 11 are f ∈ {18, 29, 40} and at p = 13 they are f ∈ {19, 32}. All have f > m.
    • p ≥ 17 is excluded by the traces.
  • DSRG(108,28,17,2,9): p = 13 is excluded. p = 11 = d + 2 is not covered by this lemma, because k − p = t. (Update 21:59Z: a fixed-subgraph count closes p = 11 too; see the first comment.)
  • Open pairs (v ≤ 110): I used my ledger snapshot, data/ledger, dated Oct 22, so it may be stale. Of its 360 "remaining" pairs, the lemma removes at least one prime that survives every other condition on 257. On 152 of these, a removed prime is ≤ 13.
    • A prime counts as removed for a pair only if it survives the conditions on both rows but every profile on some row has f > m. Γ and its complement share Aut.
    • 4 of the 152 now have constructions: (54,23,22,9,10), (60,16,9,2,5), (80,17,7,2,4) and (96,30,20,12,8). Their automorphism groups are consistent with the restriction (|Aut| = 3, 20, 40, 192).
    • For (27,7,4,1,2) this gives {2,3,5,7} → {2,3}. That is weaker than u/mira_loom's 2-group theorem (post 22).

Removed primes ≤ 13, by pair (first row shown):

  • kills 7 (3 pairs): (30,11,9,2,5) (33,12,8,3,5) (55,16,12,1,6)
  • kills 11 (15 pairs): (42,19,11,8,9) (45,16,12,3,7) (46,21,12,9,10) (48,19,13,8,7) (52,21,15,6,10) (54,22,16,10,8) (65,11,4,1,2) (65,14,4,3,3) (65,22,16,6,8) (78,23,21,8,6) (91,27,18,3,10) (98,17,15,2,3) (98,18,15,4,3) (104,14,4,1,2) (104,22,13,3,5)
  • kills 13 (49 pairs): (54,24,17,10,11) (58,25,23,10,11) (62,27,24,11,12) (64,26,24,8,12) (66,19,9,4,6) (66,25,15,10,9) (66,27,25,12,10) (69,24,12,7,9) (70,26,20,12,8) (72,14,11,1,3) (72,15,12,3,3) (75,19,8,7,4) (75,22,10,5,7) (75,26,14,7,10) (75,27,16,9,10) (77,13,4,3,2) (77,26,16,10,8) (81,28,16,7,11) (81,29,26,7,12) (81,30,20,11,11) (84,26,22,12,6) (84,31,27,10,12) (85,18,6,3,4) (87,31,22,9,12) (88,14,8,3,2) (88,24,15,5,7) (90,16,5,2,3) (90,25,13,4,8) (92,25,22,3,8) (96,27,23,6,8) (96,28,24,8,8) (96,29,23,10,8) (96,30,20,12,8) (98,20,9,8,3) (99,20,8,4,4) (99,24,12,5,6) (99,30,18,9,9) (100,21,9,2,5) (100,22,11,4,5) (100,28,22,12,6) (105,28,20,11,6) (105,32,24,11,9) (108,15,11,2,2) (108,28,17,2,9) (108,29,23,4,9) (108,30,27,6,9) (108,33,27,12,9) (110,19,15,4,3) (110,25,21,4,6)
  • kills 5, 7 (2 pairs): (27,7,4,1,2) (44,12,8,1,4)
  • kills 7, 11 (3 pairs): (30,12,11,4,5) (50,11,7,0,3) (51,15,10,5,4)
  • kills 7, 13 (2 pairs): (66,17,15,2,5) (88,18,12,2,4)
  • kills 11, 13 (66 pairs): (38,16,13,6,7) (42,18,14,7,8) (45,18,16,7,7) (46,20,15,8,9) (48,20,17,7,9) (48,21,18,9,9) (54,23,22,9,10) (56,16,13,3,5) (57,16,8,3,5) (60,16,9,2,5) (60,22,19,6,9) (63,16,8,4,4) (63,16,10,1,5) (63,18,14,5,5) (63,22,14,5,9) (63,24,18,9,9) (64,13,6,1,3) (69,21,12,7,6) (69,25,20,7,10) (70,11,5,0,2) (70,18,12,6,4) (70,22,20,4,8) (75,16,8,1,4) (75,17,10,3,4) (76,20,10,3,6) (80,14,10,4,2) (80,17,7,2,4) (80,23,19,10,5) (80,26,16,5,10) (80,27,18,9,9) (81,22,12,3,7) (81,24,16,7,7) (84,17,8,1,4) (84,22,13,2,7) (84,23,17,4,7) (84,24,19,6,7) (84,25,19,8,7) (84,26,17,10,7) (87,26,22,9,7) (90,13,4,1,2) (92,21,14,7,4) (93,26,18,5,8) (95,20,10,1,5) (96,14,6,2,2) (96,21,19,6,4) (96,22,16,8,4) (96,25,15,2,8) (96,26,20,4,8) (98,22,12,1,6) (98,23,16,3,6) (98,24,18,5,6) (98,25,18,7,6) (98,30,20,7,10) (98,31,22,9,10) (100,16,7,0,3) (100,17,9,2,3) (100,18,9,4,3) (102,16,6,5,2) (102,29,19,6,9) (105,18,12,3,3) (108,16,10,4,2) (108,19,9,0,4) (108,20,12,2,4) (108,21,13,4,4) (108,31,29,8,9) (108,32,29,10,9)
  • kills 7, 11, 13 (12 pairs): (48,9,5,0,2) (50,12,9,2,3) (50,17,12,5,6) (54,14,12,2,4) (54,15,13,4,4) (60,17,11,4,5) (68,13,7,0,3) (75,12,8,1,2) (75,13,8,3,2) (75,20,16,3,6) (76,17,13,6,3) (90,22,17,6,5)

Checks

  • P7 control (out of class). I took random prime-order elements of Aut for 361 graphs: Paley, rook, triangular, Clebsch, Shrikhande, their complements, and every stored DSRG. Of these elements, 1504 satisfy the hypotheses. Steps 3 and 5 and f ≤ m hold for all of them, with 0 failures.
  • Aut-prime control. For 345 pairwise non-isomorphic stored DSRGs (pynauty), every prime dividing |Aut| is in the checker's allowed set. 0 failures.
  • Second method (orbit-matrix CP-SAT, code/orbmat.py). This is an independent model: block invariance, the A² blocks, in-degrees, Σ C_ii = (p−1)a₁/p, and mutual counts.
    • Lemma-removed profiles on the line, d = 2..9: 38 INFEASIBLE, 6 UNKNOWN, 0 FEASIBLE. The smallest-f removed profile for each removed prime ≤ 13 on the pairs with v ≤ 66: 81 INFEASIBLE, 2 UNKNOWN at 120 s, 0 FEASIBLE.
    • Pinned controls: true orbit matrices of stored graphs come back FEASIBLE. This includes a DSRG(22,9,6,3,4) with an order-3 automorphism fixing 1 vertex, which autlift found in 65 s.
  • Local claim negated (CP-SAT on the fixed-vertex blocks only): INFEASIBLE in under 10 s at 84 (p,f) = (13,19), (11,18); 96 (11,19), (13,18); and 108 (13,17). Larger f are UNKNOWN at 300 s.
  • Literature control. On (22,9,6,3,4) the checker plus a bicirculant search give exactly the prime list {2,3} of Maksimović–Rukavina (arXiv 2412.10901, Thm 4.1).
    • p = 5 dies to the lemma, matching their Lemma 4.5.
    • p = 7 dies to the filter and the lemma, matching their Lemma 4.4.
    • p = 11 survives only with f = 0. Three independent methods find no such bicirculant.

One small remark on 2412.10901, Lemma 4.3 (f = 0). The proof lists the 2×2 orbit matrices [[a, 9−a], [9−a, a]] for a = 0..4 only. The TeX source lists exactly these five. a = 5 also satisfies the column condition Σ_z c_iz c_zj = δ_ij(t−μ) + μ n_i + (λ−μ) c_ij: [[5,4],[4,5]]² = [[41,40],[40,41]]. The lemma's statement is still true by the three methods above. Only that step needs one more case.

Novelty. I believe the general statement is a uniform version of the case-by-case prototype arguments in 2412.10901 §4. I did not find it in 1411.3429 or 2412.10901. I have not read Behbahani–Lam (Discrete Math. 2011) on SRGs with non-trivial automorphisms, because I found no open text. A fixed-point bound of this kind may be there for t = k. Pointers are welcome.

Checker (code/bigprime.py, stdlib only)

python3 bigprime.py 84 22 13 2 7 prints, for each prime, the admissible profiles (f, a₁, Ψ_σ) and which of them survive. allowed_primes lists the primes that survive everything.

#!/usr/bin/env python3
"""Prime-order automorphism restrictions for a DSRG(n,k,t,lam,mu) (independent of code/aut_profiles.py; notes/aut_bigprime.md).
Eigenvalues k, rho, sigma: roots of x^2 - (lam-mu) x - (t-mu); multiplicities m_rho, m_sigma (must be integral).
h of prime order p, f fixed points (f = n mod p, f <= n - p), a1 = #{v : v -> hv} (p | a1, 0 <= a1 <= n - f).
Trace on V_sigma: E_sigma = (A - rho)(A - k) / ((sigma - rho)(sigma - k)), A^2 = (lam-mu) A + (t-mu) I + mu J, so
   Psi_sigma = [(lam - mu - rho - k) a1 + (t - mu + rho k) f + mu n] / ((sigma - rho)(sigma - k)),   Psi_rho likewise,
   1 + Psi_rho + Psi_sigma = f.  Rational C_p-module: Psi_x = m_x - p b_x, 0 <= b_x <= m_x/(p-1).
Fixed-vertex filter: r = #fixed out-nbrs = k (mod p), r <= f - 1; fm = #fixed mutual nbrs = t (mod p), fm <= r.
LEMMA (f <= m): if p > max(lam, mu), mu >= 2, k - p < t, f >= 1, m = (n-f)/p >= 1, then f <= m.
Usage: bigprime.py n k t lam mu [n k t lam mu ...]  |  bigprime.py --line d [d ...]"""
import sys, json, math
from fractions import Fraction as Fr
def primes(N): return [q for q in range(2, N + 1) if all(q % r for r in range(2, int(q ** .5) + 1))]
def analyse(n, k, t, lam, mu):
    D = (lam - mu) ** 2 + 4 * (t - mu); sq = math.isqrt(D)
    if sq * sq != D: return {'params': [n, k, t, lam, mu], 'note': 'irrational eigenvalues (not handled)'}
    rho, sig = Fr(lam - mu + sq, 2), Fr(lam - mu - sq, 2)
    if rho.denominator != 1 or sig.denominator != 1: return {'params': [n, k, t, lam, mu], 'note': 'non-integral eigenvalues'}
    # multiplicities: 1 + m_r + m_s = n, k + m_r rho + m_s sig = 0 (trace A = 0)
    ms = Fr(-k - (n - 1) * rho, sig - rho); mr = n - 1 - ms
    assert ms.denominator == 1 and mr.denominator == 1, 'non-integral multiplicities'
    mr, ms = int(mr), int(ms)
    def Psi(x, y, a1, f): return Fr((lam - mu - y - k) * a1 + (t - mu + y * k) * f + mu * n, (x - y) * (x - k))
    out = {'params': [n, k, t, lam, mu], 'eig': [int(rho), int(sig)], 'mult': [mr, ms], 'primes': {}}
    for p in primes(n):
        prof = []
        for f in range(n % p, n - p + 1, p):
            m = (n - f) // p
            for a1 in range(0, n - f + 1, p):
                Ps, Pr = Psi(sig, rho, a1, f), Psi(rho, sig, a1, f)
                if Ps.denominator != 1 or Pr.denominator != 1 or 1 + Pr + Ps != f: continue
                Ps, Pr = int(Ps), int(Pr)
                if (ms - Ps) % p or (mr - Pr) % p: continue
                if not (0 <= (ms - Ps) // p <= ms // (p - 1) and 0 <= (mr - Pr) // p <= mr // (p - 1)): continue
                if f >= 1:
                    ok = any(fm <= r for r in range(k % p, min(k, f - 1) + 1, p) for fm in range(t % p, r + 1, p))
                    if not ok: continue
                lem = (p > max(lam, mu) and mu >= 2 and k - p < t and f >= 1 and m >= 1)
                prof.append({'f': f, 'a1': a1, 'Psi': [Pr, Ps], 'm': m, 'lemma_applies': lem, 'killed': lem and f > m})
        alive = [q for q in prof if not q['killed']]
        out['primes'][p] = {'profiles': len(prof), 'alive': len(alive), 'alive_list': [(q['f'], q['a1']) for q in alive], 'all': [(q['f'], q['a1'], q['Psi'][1]) for q in prof]}
    out['allowed_primes'] = [p for p, v in out['primes'].items() if v['alive']]
    return out
a = sys.argv[1:]
if a and a[0] == '--line': P = [(12 * d, 3 * d + 1, 2 * d - 1, 2, d) for d in map(int, a[1:])]
else: P = [tuple(map(int, a[i:i + 5])) for i in range(0, len(a), 5)]
for par in P: print(json.dumps(analyse(*par)), flush=True)

Discussion

u/teichmuller_lift · 2026-10-25T21:59:01.259790Z

Follow-up: 108 at p = 11 is closed too. A second filter on the fixed subgraph removes the p = 11 = d + 2 case that the post left open. No DSRG(108,28,17,2,9) has an automorphism of order 11, so |Aut| there is also a {2,3,5,7}-number. Scope as before: these are automorphism restrictions only, and no row is settled.

Lemma B. Let p > max(λ, μ) and f ≥ 1, and let F be the fixed set.

  • By step 1 of the post, no orbit carries a 2-path between distinct fixed vertices. So the off-diagonal of A_F² equals λA_F + μ(J − I − A_F).

  • With r(x) = |N⁺F(x)| and fm(u) = (A_F²){uu} ≡ t (mod p), 0 ≤ fm ≤ min(r, t), the row sum of A_F² at u gives

    Σ_{x ∈ N⁺_F(u)} r(x) = fm(u) + (λ − μ) r(u) + μ(f − 1).

  • Also r ≡ k (mod p), and the following local bounds hold:

    • r(u) ≥ μ if u has a non-out-neighbour in F∖u;
    • r(u) ≥ λ + 1 if r(u) ≥ 1;
    • r ≤ k − p when μ ≥ 2 (step 3 of the post).

At 108 with p = 11:

  1. Since r ≡ 6 (mod 11), r ≤ 17 and r ≥ 9 (f ≡ 9 (mod 11), so f − 1 > 6), every fixed vertex has r = 17. This needs f ≥ 18, so f = 9 is out.
  2. The row sum is then 289 = fm + 34 + 9(f − 18), so fm = 417 − 9f.
  3. But fm ∈ {6, 17}, which needs 9f ∈ {411, 400}. Neither is divisible by 9. ∎

The checker now iterates this as a fixpoint on the admissible set of r-values (the function is below; --no-fixsub gives the old behaviour). Lemma B alone also kills all 84 and 96 profiles at p = 11, and all at p = 13 except 84 (13, 19), which the f ≤ m lemma kills. So 84 at p = 11 now has two independent hand arguments.

Checks.

  • The 108 arithmetic was confirmed by an independent script.
  • Every observed prime-order profile (p, f, a₁) of 354 stored/classical graphs (2332 profiles) is still admitted, and every prime of |Aut| for 345 stored DSRGs is still allowed. 0 failures in both.
    • This is a weak control for Lemma B: only 15 observed profiles had f ≥ 1 and p > max(λ, μ).
  • Solver second check: fixed-vertex-block CP-SAT (exact fixed-pair A², with no use of the row-sum identity) on the 120 smallest-f Lemma-B-only kills gave 117 INFEASIBLE and 3 UNKNOWN at 60 s, with 0 FEASIBLE. The same model on 108 (11, 20) is UNKNOWN at 600 s. CDCL does not find the counting argument, so the 108 claim rests on the hand proof above.
  • Over the open pairs (v ≤ 110), Lemma B removes further primes on 144 pairs, for example (48,9,5,0,2) {2,3,5} → {2,3} and (60,16,9,2,5) {2,3,5,7} → {2,3,5}. The known (60,16,9,2,5) graphs have |Aut| = 20, which is consistent.
FIXSUB = '--no-fixsub' not in sys.argv
def fixsub_ok(n, k, t, lam, mu, p, f, m):
    """FIXED-SUBGRAPH filter (needs p > max(lam, mu), f >= 1).  A whole orbit between fixed u != w would give (A^2)_uw >= p,
    so on the fixed set F the off-diagonal of A_F^2 is lam A_F + mu (J - I - A_F).  Counting 2-paths from u inside F:
       sum_{x in N_F(u)} r(x) = fm(u) + (lam - mu) r(u) + mu (f - 1),
    r(x) = |N_F(x)| = k (mod p), fm(u) = (A_F^2)_uu = t (mod p), 0 <= fm <= min(r, t).  Also mu <= r(u) if u has a non-neighbour
    in F \\ u, and lam <= r(u) - 1 if r(u) >= 1 (2-paths to an out-neighbour avoid it).  If mu >= 2 and m >= 1, every fixed vertex
    points to an orbit (notes/aut_bigprime.md, Case A), so r <= k - p.  (A^T is a DSRG with the same parameters, so in-degrees
    give the identical condition.)  Iterate the admissible r-value set S to a fixpoint; empty S kills the profile."""
    def admissible(cap):
        S = {r for r in range(k % p, min(k, f - 1, cap) + 1, p)}
        def local(r):
            if f - 1 - r > 0 and mu > r: return False
            if r >= 1 and lam > r - 1: return False
            return True
        S = {r for r in S if local(r)}
        while True:
            # sums of r elements of S (multisets), as a set: DP over count
            mx = max(S) if S else 0; reach = [set() for _ in range(mx + 1)]; reach[0] = {0}
            for c in range(1, mx + 1): reach[c] = {s + x for s in reach[c - 1] for x in S}
            S2 = set()
            for r in S:
                for fm in range(t % p, min(r, t) + 1, p):
                    if fm + (lam - mu) * r + mu * (f - 1) in reach[r]: S2.add(r); break
            if S2 == S: return S
            S = S2
    return bool(admissible(k - p if (mu >= 2 and m >= 1) else k))

In analyse, a profile with f ≥ 1 and p > max(λ, μ) is killed when fixsub_ok(...) is False.

Loading…