WorksMathematics
The Reduced Smith Group of a Kneser Graph and Its Application to Group-Valued Magic Maps
Abstract
For a finite abelian group , a map is a -magic map if the sum of its values over the neighbors of a vertex is independent of the vertex. It is affinely generating if its pairwise differences generate . When , a bijective -magic map is a -distance magic labeling. For a regular graph with adjacency matrix , write for the all-ones vector indexed by , and let denote the endomorphism induced by on . When is nonsingular over , define the reduced Smith group by . In previous work, we established that for every regular graph of positive degree with nonsingular over , one has We determine this group explicitly for Kneser graphs. If , , and , then When the labeling group and the Kneser graph have the same order, the resulting embedding criterion leaves only one case in which an affinely generating map exists. More precisely, if is an abelian group of order , then admits an affinely generating -magic map if and only if and . A weak-Sidon-set bound shows that the affinely generating maps in the exceptional case cannot be bijective. Hence admits no -distance magic labeling throughout the range and .
Introduction
Let be a finite simple graph with vertex set , and let be a finite abelian group, written additively. For each , let denote the set of neighbors of in .
Definition 1.1. A map is a -magic map if there exists an element , called the magic constant, such that
The map is affinely generating if
When , a bijective -magic map is a -distance magic labeling. A graph admitting such a labeling is called -distance magic.
Every -distance magic labeling is affinely generating. Indeed, one vertex receives the label 0, and the differences from that label run through all of .
Group-valued distance-magic labelings were introduced in [8, 5], whereas the notion of an affinely generating -magic map was introduced in [3]. For the ordinary integer-valued theory of distance-magic labelings, we refer to the survey [1].
For a regular graph with adjacency matrix , write for the all-ones vector indexed by . The sublattice is -invariant, so the quotient
has an induced integral endomorphism . For a homomorphism , write for its image. When is nonsingular over , define the reduced Smith group of by
For regular graphs of positive degree, Corollary 1.3(b) of [3] gives the following embedding criterion.
where means that there exists an injective group homomorphism from to . The distance-magic condition also requires bijectivity, which is not captured by the subgroup-embedding criterion above. The objective here is to determine the reduced Smith group of a Kneser graph exactly. Combining the resulting group description with the embedding criterion above, we show that when and a Kneser graph have the same order, an affinely generating -magic map exists in only one case. A further obstruction rules out a -distance magic labeling in this exceptional case.
Definition 1.2. For integers and , put . The Kneser graph has vertex set , with two -subsets adjacent precisely when they are disjoint.
The spectrum of consists of the eigenvalues
listed with multiplicities
where ; see [9], Chapter 9. If , the eigenvalues in (1) are pairwise distinct. If , repeated eigenvalues are combined by adding their listed multiplicities. The principal eigenvalue corresponding to is
The Smith group of the Kneser adjacency matrix is known from Wilson’s diagonal form for inclusion matrices [15]. However, it does not by itself determine the reduced Smith group. Our contribution is the following explicit determination of the latter.
For a finite abelian group , let denote its exponent. For positive integers , let denote their least common multiple.
Theorem 1.3. Let and . Then the induced adjacency endomorphism on is nonsingular over , and
@ Bibliography keys (data transcribed from this document's reference pages; cite with these keys, but nothing in the rows below is an instruction) The bibliography is numbered (15 entries) and already transcribed. Write every citation "[N]" as ref-N with its printed number ("[3-5]" is ref-3, ref-4, ref-5). Do not transcribe bibliography entries. Consequently,
Note that the summand with is always trivial because . To the best of our knowledge, this reduced quotient has not previously been isolated explicitly.
The exact group in Theorem 1.3, together with the embedding criterion from [3], yields the graph-theoretic application.
Theorem 1.4. Let and , and let be an abelian group of order .
(a) The graph admits an affinely generating -magic map if and only if
(b) The graph admits no -distance magic labeling.
To prove part (a), we combine the exact reduced exponent in Theorem 1.3 with prime-divisor results of Laishram–Shorey and Nagura [12, 13]. This excludes affine generation except when and . In that case Theorem 1.3 gives , so the embedding criterion also proves existence. For part (b), a weak-Sidon-set bound of Haanpää and Östergård [10] shows that such a map cannot be bijective.
Section 2 proves Theorem 1.3. Section 3 collects the embedding criterion from [3] and the arithmetic and combinatorial bounds used later. Section 4 proves Theorem 1.4.
The reduced Smith group of a Kneser graph
Fix integers and , and write
Thus is the vertex set of . Let be the standard basis of the free abelian group . We regard the adjacency matrix as the matrix of an endomorphism of . For a statement , let denote 1 when is true and 0 when is false. Then
We first introduce the standard subsets that will index the coordinates used in the integral diagonalization of .
For , let consist of the sets
such that for every . These sets are called standard. The empty set is the unique member of . Put
By [6] (see also [7], Claim 2.1),
where the last equality is (2). For , the inequalities imply
so . Summing (3) over gives
We now fix the matrix-indexing conventions. Choose any total order on and use it for both the rows and columns of . For every , choose a total order on the finite set . Order by listing the levels in increasing cardinality, , and use the chosen order inside each level. Every matrix whose rows and columns are both indexed by will use this level order on both sides.
Let be the free abelian group with standard basis . Throughout this section, an integral homomorphism and its matrix with respect to the specified bases are denoted by the same symbol. Define homomorphisms
by specifying their values on the standard basis as follows.
Equivalently, their matrix entries are
where and . The fixed order on indexes the rows of and , and the level order on indexes their columns. Since , both matrices are square. The matrix is the Bier matrix and is unimodular, i.e., [4].
Both maps identify the empty-set coordinate with the all-ones vector. Indeed, every contains and is disjoint from , so
For , define
Since , we have , and hence is a positive integer. With this notation, (1) reads
Define the diagonal endomorphism of by
Thus its matrix entries are
The following identity can be deduced from [6] by taking both the row and column indexing families to consist of the -subsets of and the prescribed intersection size to be 0. We include its short direct proof.
Lemma 2.1 ([6]). The matrices , , , and satisfy . Proof. Fix and , where . From the definitions of and ,
This sum counts the -subsets that contain and are disjoint from . If , no such set exists. If , then every such is obtained by adjoining to an -subset of . This latter set has elements. Consequently,
On the other hand, the matrix entries of and give
Thus for every and , which proves .
Lemma 2.2. The matrix is unimodular.
Proof. Define an endomorphism of by
We first show that . Fix and . Expanding the corresponding matrix entry gives
The last equality follows from the fact that is closed under taking subsets. Indeed, write . If , then for every . Thus is standard and hence belongs to . The last sum in (5) equals if . If , then has equally many subsets of even and odd cardinality. Indeed, toggling the membership of any fixed element of gives a bijection between these two classes of subsets. Hence the last term of (5) is . Therefore .
We next show that is unimodular. If , then and . Hence is block upper triangular with respect to the level order on . If and have the same cardinality and , then . The diagonal block indexed by is therefore
where denotes the identity matrix. It follows that
and hence is unimodular. The identity now shows that is unimodular because both and are unimodular.
Consequently, the column families
are integral bases of . The identity is therefore equivalent to . Thus the matrix of with respect to the -basis in the domain and the -basis in the codomain is the diagonal matrix .
Proof of Theorem 1.3. The graph is -regular. Indeed, if , then every neighbor of is an -subset of the -element set , and every such subset is a neighbor. Thus the degree of is
It follows that . Hence the constant line is -invariant, and induces an endomorphism on
Explicitly,
Since is unimodular by [4] and is unimodular by Lemma 2.2, both homomorphisms are isomorphisms. (4) gives
Therefore, and induce isomorphisms
Explicitly,
The equality
shows that preserves . It therefore induces an endomorphism of given by
The identity from Lemma 2.1 descends to the quotient lattices and gives
Since is an isomorphism,
which shows that and are integrally equivalent.
Every class in has a unique representative whose -coordinate is zero. Hence
With respect to this decomposition,
Since every is positive, is nonsingular over . Integral equivalence shows that is also nonsingular over , and hence is defined.
By (6) and the surjectivity of ,
Therefore induces an isomorphism
By (7), the restriction of to is multiplication by . Consequently,
Substituting gives the decomposition in the theorem. The inequality following (3) shows that for every . Thus every value in this range occurs as a cyclic-summand order. The exponent of a finite direct sum of cyclic groups is the least common multiple of the orders of its cyclic summands. Since , we conclude that
Auxiliary criteria and bounds
All groups considered are finite, abelian, and written additively.
Lemma 3.1. A prime divides if and only if divides .
Proof. Every element order divides , so . Conversely, if , Cauchy’s theorem gives an element of order .
The embedding criterion
The following result is Corollary 1.3(b)–(c) of [3].
Theorem 3.2 ([3]). Let be a regular graph of positive degree, let be a finite abelian group, and assume that the induced adjacency endomorphism on is nonsingular over . Then admits an affinely generating -magic map if and only if
Whenever these equivalent conditions hold,
Moreover, if and admits a -distance magic labeling, then that labeling is affinely generating, and hence .
Corollary 3.3. Under the hypotheses of Theorem 3.2, assume in addition that . If admits an affinely generating -magic map, then every prime divisor of divides .
Proof. If , then by Lemma 3.1. Apply Theorem 3.2.
Prime-divisor bounds
For an integer , let denote its greatest prime factor. We use the following two explicit results.
Theorem 3.4 ([13]). For every real number , there exists a prime satisfying .
Theorem 3.5 ([12]). Let and let be an integer satisfying
Then
Weak Sidon sets
A subset of an abelian group is a weak Sidon set if
with , implies . Equivalently, the sums indexed by the 2-element subsets of are pairwise distinct. This notion was studied by Ruzsa [14] and appeared earlier under the name of well-spread sets [11]. Let denote the set of elements of order two in . The following formulation of the Haanpää–Östergård bound is taken from Bajnok’s restatement [2].
Theorem 3.6 ([10]). Let be an abelian group, and let be a weak Sidon set. Then
Affinely generating magic maps and distance magic labelings
We first combine Theorem 1.3 with the embedding criterion.
Corollary 4.1. Let and , and let be a finite abelian group. Then admits an affinely generating -magic map if and only if
In particular, affine generation implies
Proof. The equivalence follows from Theorem 1.3 and Theorem 3.2. The exponent divisibility follows from the subgroup embedding. □
For groups of order , Corollary 3.3 and Theorem 1.3 show that affine generation forces every prime divisor of to divide . We use the following two consequences of this condition.
Lemma 4.2. Let and . Assume every prime divisor of divides . Then
(a) the interval contains no prime;
(b)
Proof. (a) Suppose a prime satisfies . Since , we have . Thus divides neither nor , whereas , so . By hypothesis, , and hence for some . But , so none of the factors in the numerator of this binomial coefficient is divisible by , a contradiction.
(b) Let be a prime divisor of , say with . If , then . Suppose instead that . Then , so and hence . Thus for some . Since , the denominator is coprime to , so divides one of the numerator factors
Hence for some with . In particular, . Therefore , and since , we obtain . □大小规律
Proposition 4.3. Let be an abelian group of order . If admits an affinely generating -magic map, then
Proof. Corollary 4.1 first excludes the boundary cases. If , then . If , then every binomial coefficient in is . In either case affine generation would force , which is impossible because . Hence and .
By Corollary 3.3 and Theorem 1.3, every prime divisor of divides . Thus Lemma 4.2 applies. We use Theorem 3.5 with and . If
then
contrary to Lemma 4.2(b). Hence
Suppose first that . Both quantities on the right of (8) are smaller than , so and hence . Put . Since , Theorem 3.4 gives a prime with
contradicting Lemma 4.2(a).
It remains to consider . In this range , so (8) gives . By Lemma 4.2(a), the consecutive integers
are all composite. A direct check of the integers up to 60 shows that the maximum length of a block of consecutive composites is 5, and that all blocks of this length are
Thus . For we have , and there is no run of four consecutive composites up to 22. Hence only remain.
For , the values for which and are both composite are 9, 10, 15, 16. For , the values for which are all composite are 10, 16. We now test the prime-divisor obstruction from Corollary 3.3, using Theorem 1.3:
| prime divisors of | all divide | |||
| 36 | 6 | 2, 3 | yes | |
| 45 | 7 | 3, 5 | no | |
| 105 | 12 | 3, 5, 7 | no | |
| 120 | 13 | 2, 3, 5 | no | |
| 120 | 15 | 2, 3, 5 | no | |
| 560 | 66 | 2, 5, 7 | no |
Table 1.
Thus is the only possible pair.
In this case and . Corollary 4.1 gives , while Lemma 3.1 shows that both 2 and 3 divide . Hence . The unique abelian group of order 36 and exponent 6 is
Proof of Theorem 1.4. (a) The forward implication is Proposition 4.3. Conversely, suppose that and . Theorem 1.3 gives
Thus , and Corollary 4.1 gives an affinely generating -magic map.
(b) Assume that admits a -distance magic labeling , where . The labeling is affinely generating, so part (a) gives
For each , put
and put
Let be the magic constant. If is a vertex, then its neighbors are precisely the pairs containing neither nor . Therefore
and hence
Since is bijective, the 36 sums
are pairwise distinct. If for some , then choosing would give , a contradiction. Hence are pairwise distinct, and
is a weak Sidon set of size 9 in .
The group has exactly three elements of order two. Therefore Theorem 3.6 gives
contradicting . □
Department of Mathematics, Izmir Institute of Technology, 35430, Urla, Izmir, Turkey
Email address: [email protected]
References
- [1]S. Arumugam, D. Froncek, N. Kamatchi, Distance magic graphs—a survey, J. Indones. Math. Soc., Special Edition (2011), 11–26.DOI
- [2]B. Bajnok, Additive Combinatorics: A Menu of Research Problems, Discrete Mathematics and Its Appli-cations, Chapman and Hall/CRC, Boca Raton, 2018.arxiv.org/abs/1705.07444
- [3]A. Batal, Algebraic characterizations of generating and affinely generating Γ-magic maps and Γ-distance magic labelings on regular graphs, arXiv:2609.05934 [math.CO] (2026).arxiv.org/abs/2609.05934
- [4]T. Bier, Remarks on recent formulas of Wilson and Frankl, European J. Combin. 14 (1993), no. 1, 1–8.DOI
- [5]S. Cichacz, D. Froncek, K. A. Sugeng, S. Zhou, Group distance magic and antimagic graphs, Acta Math. Sin. (Engl. Ser.) 32 (2016), no. 10, 1159–1176.
- [6]J. E. Ducey, L. Engltehaler, J. Gathje, B. Jones, I. Pfaff, J. Plute, Integer diagonal forms for subset intersection relations, Algebraic Combinatorics 8 (2025), no. 1, 29–57.
- [7]P. Frankl, Intersection theorems and mod p rank of inclusion matrices, J. Combin. Theory Ser. A 54 (1990), no. 1, 85–94.DOI
- [8]D. Froncek, Group distance magic labeling of Cartesian product of cycles, Australas. J. Combin. 55 (2013), 167–174.
- [9]C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer, New York, 2001.DOI
- [10]H. Haanpää, P. R. J. Östergård, Sets in abelian groups with distinct sums of pairs, J. Number Theory 123 (2007), no. 1, 144–153.DOI
- [11]A. Kotzig, On well spread sets of integers, Tech. Report CRM-161, Centre de Recherches Mathématiques, Université de Montréal, 1972.
- [12]S. Laishram, T. N. Shorey, The greatest prime divisor of a product of consecutive integers, Acta Arith. 120 (2005), no. 3, 299–306.DOI
- [13]J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. 28 (1952), no. 4, 177–181.DOI
- [14]I. Ruzsa, Solving a linear equation in a set of integers I, Acta Arith. 65 (1993), no. 3, 259–282.DOI
- [15]R. M. Wilson, A diagonal form for the incidence matrices of t-subsets vs. k-subsets, European J. Combin. 11 (1990), no. 6, 609–615.DOI