Publication Date:
2019
Description:
〈p〉Publication date: Available online 3 July 2019〈/p〉
〈p〉〈b〉Source:〈/b〉 Discrete Mathematics〈/p〉
〈p〉Author(s): Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan〈/p〉
〈h5〉Abstract〈/h5〉
〈div〉〈p〉Recently, Grynkiewicz et al. (2013), using tools from additive combinatorics and group theory, proved necessary and sufficient conditions under which the linear congruence 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si1.svg"〉〈mrow〉〈msub〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈msub〉〈mrow〉〈mi〉x〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈mo linebreak="goodbreak" linebreakstyle="after"〉+〈/mo〉〈mo linebreak="goodbreak" linebreakstyle="after"〉⋯〈/mo〉〈mo linebreak="goodbreak" linebreakstyle="after"〉+〈/mo〉〈msub〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mi〉k〈/mi〉〈/mrow〉〈/msub〉〈msub〉〈mrow〉〈mi〉x〈/mi〉〈/mrow〉〈mrow〉〈mi〉k〈/mi〉〈/mrow〉〈/msub〉〈mo linebreak="goodbreak" linebreakstyle="after"〉≡〈/mo〉〈mi〉b〈/mi〉〈mspace width="0.334em"〉〈/mspace〉〈mrow〉〈mo〉(〈/mo〉〈mo〉mod〈/mo〉〈mspace width="0.334em"〉〈/mspace〉〈mi〉n〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈/math〉, where 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si2.svg"〉〈mrow〉〈msub〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈mo〉,〈/mo〉〈mo〉…〈/mo〉〈mo〉,〈/mo〉〈msub〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mi〉k〈/mi〉〈/mrow〉〈/msub〉〈mo〉,〈/mo〉〈mi〉b〈/mi〉〈mo〉,〈/mo〉〈mi〉n〈/mi〉〈/mrow〉〈/math〉
(〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si3.svg"〉〈mrow〉〈mi〉n〈/mi〉〈mo linebreak="goodbreak" linebreakstyle="after"〉≥〈/mo〉〈mn〉1〈/mn〉〈/mrow〉〈/math〉) are arbitrary integers, has a solution 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si4.svg"〉〈mrow〉〈mrow〉〈mo〉〈〈/mo〉〈msub〉〈mrow〉〈mi〉x〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈mo〉,〈/mo〉〈mo〉…〈/mo〉〈mo〉,〈/mo〉〈msub〉〈mrow〉〈mi〉x〈/mi〉〈/mrow〉〈mrow〉〈mi〉k〈/mi〉〈/mrow〉〈/msub〉〈mo〉〉〈/mo〉〈/mrow〉〈mo linebreak="goodbreak" linebreakstyle="after"〉∈〈/mo〉〈msubsup〉〈mrow〉〈mi mathvariant="double-struck"〉Z〈/mi〉〈/mrow〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈mrow〉〈mi〉k〈/mi〉〈/mrow〉〈/msubsup〉〈/mrow〉〈/math〉 with all 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si5.svg"〉〈msub〉〈mrow〉〈mi〉x〈/mi〉〈/mrow〉〈mrow〉〈mi〉i〈/mi〉〈/mrow〉〈/msub〉〈/math〉 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 (1839), proved an explicit formula for the number of such solutions when 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si6.svg"〉〈mrow〉〈mi〉b〈/mi〉〈mo linebreak="goodbreak" linebreakstyle="after"〉=〈/mo〉〈mn〉0〈/mn〉〈/mrow〉〈/math〉, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si7.svg"〉〈mrow〉〈mi〉n〈/mi〉〈mo linebreak="goodbreak" linebreakstyle="after"〉=〈/mo〉〈mi〉p〈/mi〉〈/mrow〉〈/math〉 a prime, and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si8.svg"〉〈mrow〉〈msubsup〉〈mrow〉〈mo〉∑〈/mo〉〈/mrow〉〈mrow〉〈mi〉i〈/mi〉〈mo〉=〈/mo〉〈mn〉1〈/mn〉〈/mrow〉〈mrow〉〈mi〉k〈/mi〉〈/mrow〉〈/msubsup〉〈msub〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mi〉i〈/mi〉〈/mrow〉〈/msub〉〈mo linebreak="goodbreak" linebreakstyle="after"〉≡〈/mo〉〈mn〉0〈/mn〉〈mspace width="0.334em"〉〈/mspace〉〈mrow〉〈mo〉(〈/mo〉〈mo〉mod〈/mo〉〈mspace width="0.334em"〉〈/mspace〉〈mi〉p〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈/math〉 but 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si9.svg"〉〈mrow〉〈msub〉〈mrow〉〈mo〉∑〈/mo〉〈/mrow〉〈mrow〉〈mi〉i〈/mi〉〈mo〉∈〈/mo〉〈mi〉I〈/mi〉〈/mrow〉〈/msub〉〈msub〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mi〉i〈/mi〉〈/mrow〉〈/msub〉〈mo〉⁄〈/mo〉〈mo linebreak="goodbreak" linebreakstyle="after"〉≡〈/mo〉〈mn〉0〈/mn〉〈mspace width="0.334em"〉〈/mspace〉〈mrow〉〈mo〉(〈/mo〉〈mo〉mod〈/mo〉〈mspace width="0.334em"〉〈/mspace〉〈mi〉p〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈/math〉 for all 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" altimg="si10.svg"〉〈mrow〉〈mo〉0̸〈/mo〉〈mo linebreak="goodbreak" linebreakstyle="after"〉≠〈/mo〉〈mi〉I〈/mi〉〈mo〉⊊︀〈/mo〉〈mrow〉〈mo〉{〈/mo〉〈mn〉1〈/mn〉〈mo〉,〈/mo〉〈mo〉…〈/mo〉〈mo〉,〈/mo〉〈mi〉k〈/mi〉〈mo〉}〈/mo〉〈/mrow〉〈/mrow〉〈/math〉. 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.〈/p〉〈/div〉
Print ISSN:
0012-365X
Electronic ISSN:
1872-681X
Topics:
Mathematics
Permalink