Imprimitive association schemes and elimination theory
Pith reviewed 2026-05-15 07:44 UTC · model grok-4.3
The pith
A commutative association scheme is imprimitive exactly when it admits a multivariate P- or Q-polynomial structure with respect to an elimination-type monomial order.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
A commutative association scheme is imprimitive if and only if it admits a multivariate P- or Q-polynomial structure with respect to an elimination-type monomial order. This provides a direct bridge between the classical theory of block and quotient schemes for imprimitive association schemes and elimination theory in computational commutative algebra. For an imprimitive multivariate P- or Q-polynomial association scheme, the induced structures on the quotient and block schemes are obtained by explicit specializations, variable deletions, and rescalings, while at the level of zero-dimensional ideals the block scheme ideal is exactly an elimination ideal and the quotient scheme ideal is the (
What carries the argument
Multivariate P- or Q-polynomial structure of a commutative association scheme with respect to an elimination-type monomial order, which encodes imprimitivity by allowing variable elimination in the associated ideal of the Bose-Mesner algebra.
If this is right
- The ideal of the block scheme is precisely an elimination ideal of the original scheme's ideal.
- The ideal of the quotient scheme is obtained by adjoining the valency relations for the eliminated variables and then performing elimination.
- The associated polynomials on the quotient and block schemes arise from the original polynomials by specialization, deletion of variables, and rescaling.
- Direct products of univariate P- or Q-polynomial schemes are multivariate P- or Q-polynomial with respect to every monomial order.
Where Pith is reading between the lines
- Groebner-basis algorithms could decide imprimitivity for given commutative association schemes by testing existence of suitable elimination orders.
- The same elimination correspondence may apply to crested products and other constructions that preserve commutativity.
- Composition series of imprimitive schemes could be read off from successive elimination steps in the associated polynomial ideal.
Load-bearing premise
The standard definitions of P- and Q-polynomial structures for association schemes extend to the multivariate setting without requiring additional hidden relations among the variables.
What would settle it
A single commutative association scheme that is imprimitive yet admits no multivariate P- or Q-polynomial structure for any elimination-type monomial order, or a primitive commutative scheme that does admit such a structure.
read the original abstract
We prove that a commutative association scheme is imprimitive if and only if it admits a multivariate $P$- or $Q$-polynomial structure with respect to an elimination-type monomial order. This provides a direct bridge between the classical theory of block and quotient schemes for imprimitive association schemes and elimination theory in computational commutative algebra. For an imprimitive multivariate $P$- or $Q$-polynomial association scheme, we determine the induced multivariate polynomial structures on the quotient and block schemes and describe their associated polynomials via explicit specializations, variable deletions, and rescalings of the original associated polynomials. At the level of zero-dimensional ideals, we show that the ideal of the block scheme is exactly an elimination ideal, whereas the ideal of the quotient scheme is obtained by adjoining the valency relations for the eliminated variables and then eliminating. As applications, we study direct products and crested products from the viewpoint of multivariate polynomiality, and we characterize the schemes that are multivariate $P$- or $Q$-polynomial with respect to every monomial order as precisely the direct products of univariate $P$- or $Q$-polynomial schemes. We also discuss formal duality, composition series, and several related open problems.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that a commutative association scheme is imprimitive if and only if it admits a multivariate P- or Q-polynomial structure with respect to an elimination-type monomial order. It describes the induced multivariate polynomial structures on the associated quotient and block schemes via explicit specializations, variable deletions, and rescalings of the original polynomials. At the level of zero-dimensional ideals, the ideal of the block scheme is shown to be an elimination ideal, while the quotient scheme ideal is obtained by first adjoining valency relations for the eliminated variables and then eliminating. Applications include the study of direct products and crested products, a characterization of schemes that are multivariate P- or Q-polynomial with respect to every monomial order as precisely the direct products of univariate P- or Q-polynomial schemes, and discussions of formal duality and composition series.
Significance. If the central equivalence holds, the work establishes a concrete bridge between the classical theory of imprimitive association schemes (block and quotient constructions) and elimination theory in commutative algebra. The explicit constructions for induced structures and the ideal-theoretic interpretations (elimination ideals for blocks, valency-adjoined elimination for quotients) supply algorithmic and computational tools that were previously unavailable. The clean characterization of schemes polynomial for every monomial order as direct products of univariate ones is a notable structural result. The manuscript ships explicit specializations and ideal descriptions, which are strengths for reproducibility and further applications in algebraic combinatorics.
major comments (2)
- [Definition of multivariate P/Q-polynomial structures and the proof of the iff theorem] The definition of multivariate P- and Q-polynomial structures (with respect to elimination monomial orders) must be shown to generate precisely the Bose-Mesner ideal without extra syzygies or polynomial identities on the valencies forced by the elimination order. The 'only if' direction, which constructs the polynomials from the imprimitivity partition, requires explicit verification that the resulting relations coincide exactly with classical imprimitivity and do not strengthen the condition.
- [Ideal-theoretic interpretations for block and quotient schemes] The zero-dimensional ideal statements (block ideal equals an elimination ideal; quotient ideal obtained by adjoining valency relations then eliminating) are load-bearing for the algebraic bridge claimed in the abstract. These require detailed justification that the elimination order interacts correctly with the standard basis of the Bose-Mesner algebra for arbitrary commutative schemes, including handling of zero-dimensional cases and possible zero divisors.
minor comments (2)
- [Introduction and notation] Notation for the multivariate associated polynomials and the elimination monomial orders should be introduced with a short table or explicit comparison to the univariate case to improve readability.
- [Applications section] The applications to crested products would benefit from one concrete low-rank example (e.g., a small imprimitive scheme) showing the explicit specialization and variable deletion steps.
Simulated Author's Rebuttal
We thank the referee for the careful reading and positive evaluation of our manuscript. We address each major comment below and indicate the revisions we will make to provide the requested explicit verifications and justifications.
read point-by-point responses
-
Referee: [Definition of multivariate P/Q-polynomial structures and the proof of the iff theorem] The definition of multivariate P- and Q-polynomial structures (with respect to elimination monomial orders) must be shown to generate precisely the Bose-Mesner ideal without extra syzygies or polynomial identities on the valencies forced by the elimination order. The 'only if' direction, which constructs the polynomials from the imprimitivity partition, requires explicit verification that the resulting relations coincide exactly with classical imprimitivity and do not strengthen the condition.
Authors: We agree that the definition and both directions of the equivalence require more explicit verification to confirm exact generation of the Bose-Mesner ideal. In the revised manuscript we will insert a new lemma establishing that the ideal generated by the multivariate polynomials under an elimination order coincides with the Bose-Mesner ideal; the argument uses the compatibility of elimination orders with the standard monomial basis and the fact that no additional syzygies arise on the valencies. For the 'only if' direction we will add a direct computation that derives the polynomials from the imprimitivity partition and verifies, by substitution into the adjacency-matrix relations, that the resulting identities are precisely the classical imprimitivity relations without imposing extra constraints. revision: yes
-
Referee: [Ideal-theoretic interpretations for block and quotient schemes] The zero-dimensional ideal statements (block ideal equals an elimination ideal; quotient ideal obtained by adjoining valency relations then eliminating) are load-bearing for the algebraic bridge claimed in the abstract. These require detailed justification that the elimination order interacts correctly with the standard basis of the Bose-Mesner algebra for arbitrary commutative schemes, including handling of zero-dimensional cases and possible zero divisors.
Authors: We acknowledge that these ideal-theoretic claims need a self-contained justification. The revision will include an expanded subsection that first recalls the standard basis of the Bose-Mesner algebra, then proves that the elimination order respects this basis for any commutative scheme. For the zero-dimensional case we will show that semisimplicity of the algebra precludes nontrivial zero divisors from obstructing elimination; the block ideal is identified as the elimination ideal by direct application of the elimination theorem, while the quotient ideal is obtained by adjoining the valency relations and eliminating, with an explicit Gröbner-basis argument confirming the construction. revision: yes
Circularity Check
No significant circularity; equivalence is a direct characterization from definitions
full rationale
The central theorem establishes an if-and-only-if equivalence between imprimitivity of a commutative association scheme and the existence of a multivariate P- or Q-polynomial structure relative to an elimination monomial order. This is derived from the standard definitions of association schemes, the Bose-Mesner algebra, P/Q-polynomial structures (extended multivariately), and elimination ideals in commutative algebra. The proof constructs the associated polynomials explicitly from the imprimitivity partition for the 'only if' direction and verifies the ideal relations via specializations, variable deletions, and rescalings for the 'if' direction. No parameters are fitted to data and then renamed as predictions; no load-bearing self-citation chain is invoked to justify uniqueness or the ansatz; and the multivariate extension is shown to preserve the classical block/quotient relations without introducing hidden syzygies forced by the order. The applications to direct products, crested products, and formal duality follow as corollaries from the same explicit constructions. The derivation is therefore self-contained against the external definitions of the objects involved.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Commutative association schemes satisfy the standard axioms of a coherent configuration with commutative Bose-Mesner algebra.
- domain assumption Multivariate P- and Q-polynomial structures are defined via the existence of orthogonal polynomials in several variables compatible with the scheme's intersection numbers.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 4.1: X imprimitive iff admits ℓ-variate P-polynomial structure on D w.r.t. s-elimination monomial order (or Q-analogue)
-
IndisputableMonolith/Foundation/DimensionForcing.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Thm 4.8: block-scheme ideal is exactly the s-elimination ideal; quotient ideal obtained by adjoining valency relations then eliminating
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
An Algorithmic Approach to the Extensibility of Association Schemes
M. Arora and P.-H. Zieschang. An algorithmic approach to the extensibility of asso- ciation schemes, 2012. arXiv:1209.6312
work page internal anchor Pith review Pith/arXiv arXiv 2012
-
[2]
R. A. Bailey and P. J. Cameron. Crested products of association schemes.J. London Math. Soc. (2), 72(1):1–24, 2005
work page 2005
- [3]
-
[4]
E. Bannai and T. Ito.Algebraic combinatorics. I: Association Schemes. The Ben- jamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984
work page 1984
- [5]
- [6]
-
[7]
P.-A. Bernard, N. Cramp´ e, L. Poulain d’Andecy, L. Vinet, and M. Zaimi. Bivariate P-polynomial association schemes.Algebraic Combinatorics, 7(2):361–382, 2024
work page 2024
-
[8]
P.-A. Bernard, N. Cramp´ e, L. Vinet, M. Zaimi, and X. Zhang.m-distance-regular graphs and their relation to multivariateP-polynomial association schemes.Discrete Math., 347(12):Paper No. 114179, 21, 2024
work page 2024
-
[9]
P.-A. Bernard, N. Cramp´ e, L. Vinet, M. Zaimi, and X. Zhang. BivariateP- andQ- polynomial structures of the association schemes based on attenuated spaces.Discrete Math., 348(3):Paper No. 114332, 21, 2025
work page 2025
-
[10]
A. E. Brouwer, A. M. Cohen, and A. Neumaier.Distance-regular graphs, volume 18 ofErgebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1989
work page 1989
-
[11]
T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli. Trees, wreath products and finite Gelfand pairs.Adv. Math., 206(2):503–537, 2006
work page 2006
-
[12]
D. A. Cox, J. Little, and D. O’Shea.Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015. An introduction to computational algebraic geometry and commutative algebra
work page 2015
-
[13]
N. Cramp´ e, L. Vinet, M. Zaimi, and X. Zhang. A bivariateQ-polynomial structure for the non-binary Johnson scheme.J. Combin. Theory Ser. A, 202:Paper No. 105829, 25, 2024
work page 2024
-
[14]
B. Curtin. Inheritance of hyper-duality in imprimitive Bose-Mesner algebras.Discrete Math., 308(14):3003–3017, 2008
work page 2008
-
[15]
R. M. Damerell. Distance-transitive and distance-regular digraphs.J. Combin. The- ory Ser. B, 31(1):46–53, 1981
work page 1981
-
[16]
C. Godsil. Generalized Hamming schemes, 2010. arXiv:1011.1044
work page internal anchor Pith review Pith/arXiv arXiv 2010
-
[17]
C. D. Godsil and W. J. Martin. Quotients of association schemes.J. Combin. Theory Ser. A, 69(2):185–199, 1995
work page 1995
-
[18]
L. K. Jørgensen. Algorithmic approach to non-symmetric 3-class association schemes. InAlgorithmic algebraic combinatorics and Gr¨ obner bases, pages 251–268. Springer, Berlin, 2009
work page 2009
- [19]
-
[20]
C. W. H. Lam. Distance transitive digraphs.Discrete Math., 29(3):265–274, 1980. 45
work page 1980
-
[21]
D. A. Leonard. Nonsymmetric, metric, cometric association schemes are self-dual. J. Combin. Theory Ser. B, 51(2):244–247, 1991
work page 1991
-
[22]
W. J. Martin, M. Muzychuk, and J. Williford. Imprimitive cometric association schemes: constructions and analysis.J. Algebraic Combin., 25(4):399–415, 2007
work page 2007
-
[23]
E. Mart´ ınez-Moro. Properties of commutative association schemes derived by FGLM techniques.Internat. J. Algebra Comput., 12(6):849–865, 2002
work page 2002
- [24]
- [25]
-
[26]
H. Mizukawa and H. Tanaka. (n+ 1, m+ 1)-hypergeometric functions associated to character algebras.Proc. Amer. Math. Soc., 132(9):2613–2618, 2004
work page 2004
- [27]
-
[28]
M. Rassy and P.-H. Zieschang. Basic structure theory of association schemes.Math. Z., 227(3):391–402, 1998
work page 1998
-
[29]
J. D. H. Smith. Association schemes, superschemes, and relations invariant under permutation groups.European J. Combin., 15(3):285–291, 1994
work page 1994
-
[30]
J. D. H. Smith.An introduction to quasigroups and their representations. Studies in Advanced Mathematics. Chapman & Hall/CRC, Boca Raton, FL, 2007
work page 2007
-
[31]
D. Stanton. Someq-Krawtchouk polynomials on Chevalley groups.Amer. J. Math., 102(4):625–662, 1980
work page 1980
-
[32]
H. Suzuki. ImprimitiveQ-polynomial association schemes.J. Algebraic Combin., 7(2):165–180, 1998
work page 1998
-
[33]
E. R. van Dam, W. J. Martin, and M. Muzychuk. Uniformity in association schemes and coherent configurations: cometric Q-antipodal schemes and linked systems.J. Combin. Theory Ser. A, 120(7):1401–1439, 2013
work page 2013
-
[34]
J. s. Vidali. Eigenspace embeddings of imprimitive association schemes.Electron. J. Combin., 33(1):Paper No. 1.2, 35, 2026
work page 2026
-
[35]
Zieschang.Theory of association schemes
P.-H. Zieschang.Theory of association schemes. Springer Monographs in Mathemat- ics. Springer-Verlag, Berlin, 2005. 46
work page 2005
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.