A generalization of Schönemann's theorem via a graph theoretic method

Abstract

Recently, Grynkiewicz et al. [{\it Israel J. Math.} {\bf 193} (2013), 359--398], using tools from additive combinatorics and group theory, proved necessary and sufficient conditions under which the linear congruence $a_1{x}_1+\cdots +a_k{x}_k\equiv b(\mathrm{mod}n)$, where $a_1,\dots ,a_k,b,n$ ($n\ge 1$) are arbitrary integers, has a solution $⟨x_1,\dots ,x_k⟩\in {\mathbb{Z}}_n^k$ with all $x_i$ distinct. So, it would be an interesting problem to give an explicit formula for the number of such solutions. Quite surprisingly, this problem was first considered, in a special case, by Schönemann almost two centuries ago(!) but his result seems to have been forgotten. Schönemann [{\it J. Reine Angew. Math.} {\bf 1839} (1839), 231--243] proved an explicit formula for the number of such solutions when $b=0$, $n=p$ a prime, and ${\sum }_{i=1}^k{a}_i\equiv 0(\mathrm{mod}p)$ but ${\sum }_{i\in I}{a}_i\not\equiv 0(\mathrm{mod}p)$ for all $\varnothing \ne I\{1,\dots ,k\}$. In this paper, we generalize Schönemann's theorem using a result on the number of solutions of linear congruences due to D. N. Lehmer and also a result on graph enumeration. This seems to be a rather uncommon method in the area; besides, our proof technique or its modifications may be useful for dealing with other cases of this problem (or even the general case) or other relevant problems.

References in corpus (5)

• Restricted linear congruences
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• On an almost-universal hash function family with applications to authentication and secrecy codes
• On a restricted linear congruence
• Unweighted linear congruences with distinct coordinates and the Varshamov--Tenengolts codes

Cited by in corpus (1)

• Distinct coordinate solutions of linear equations over finite fields