Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials

Gennady Bachman · 2026

Read Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials by Gennady Bachman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17157.txt.

Introduction

Bachman studies dominant pairs in linear permutations of residue systems. A pair counts as dominant when it bounds all residues between its members, from above or from below. That analysis gives full descriptions of gap sets for binary inclusion-exclusion polynomials, which include binary cyclotomic polynomials as a key case. It also gives all possible gaps between consecutive members of two-generator numerical semigroups.

Catalog record

CREATORGennady Bachman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42748
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.17157

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials Gennady Bachman Abstract . Let p p be a given modulus, let u u be prime to p p , and consider the linear permutation u ⋅ n ( mod p ) u\cdot n\pmod{p} of the residue system modulo p p . Writing ⟨ x ⟩ p \langle x\rangle_{p} to denote the least nonnegative residue of x x modulo p p , we say that a pair of integers ( a , b ) (a,b) is a dominant pair of this permutation if either the inequality max ⁡ ( ⟨ u ​ a ⟩ p , ⟨ u ​ b ⟩ p ) < min a < n < b ⁡ ⟨ u ​ n ⟩ p \max(\langle ua\rangle_{p},\langle ub\rangle_{p})<\min_{a<n<b}\langle un\rangle_{p} , or the inequality min ⁡ ( ⟨ u ​ a ⟩ p , ⟨ u ​ b ⟩ p ) > max a < n < b ⁡ ⟨ u ​ n ⟩ p \min(\langle ua\rangle_{p},\langle ub\rangle_{p})>\max_{a<n<b}\langle un\rangle_{p} hold. The main technical part of this work gives analysis of this property of linear permutations of residue systems. We then apply this analysis to the problems that motivated it, and give (i) complete description of the gapsets of binary inclusion-exclusion polynomials Q { p , q } Q_{\{p,q\}} (which include binary cyclotomic polynomials Φ p ​ q \Phi_{pq} as its principal special case), and (ii) complete description of all possible distances between consecutive elements of a numerical semigroup ⟨ p , q ⟩ \langle p,q\rangle . 2020 Mathematics Subject Classification 11B75; 11B83; 11A05; 11A07 1. Introduction In their recent work [ 5 ] , Hong, et al. introduced a new and interesting puzzle about the behavior of coefficients of cyclotomic polynomials \Phi_{pq}(x) , where p<q are distinct odd primes. To state their problem, we need to introduce the notion of the gapset of a polynomial. Given a polynomial f(x) of degree d , write it down omitting its zero coefficients f(x)=c_{1}x^{e_{1}}+c_{2}x^{e_{2}}+\dots+c_{k}x^{e_{k}} , where 0\leq e_{1}<e_{2}<\dots<e_{k}=d and c_{i}\neq 0 . Then, if k>1 , the gapset of f is given by G(f)\coloneq\{e_{i+1}-e_{i}\} , and the individual elements are the gaps of f . Motivated by a certain application, Hong, et al, were particularly interested in the largest gap of \Phi_{pq} , denoted by g_{1}(\Phi_{pq}) . They showed that g_{1}(\Phi_{pq})=p-1 , and in the process initiated the problem of studying the gaps of \Phi_{pq} . This was followed by several new contributions investigating this and related problems. Below we describe those among them that are most relevant to the objectives of this paper. For a more comprehensive discussion and references to these contributions we refer the reader to the papers [ 1 ] and [ 8 ] . New proofs of the g_{1}(\Phi_{pq})=p-1 result were given in [ 6 , 9 , 4 ] . Zhang [ 9 ] showed that the gap p-1 occurs exactly \lfloor q/p\rfloor times. The simplest special case of the gaps problem for \Phi_{pq} occurs when q\equiv\pm 1\pmod{p} . The analysis of this case was given, among other results, by Camburu, et al, in [ 4 ] . They showed that the relation q\equiv\pm 1\pmod{p} is equivalent to the evaluation G(\Phi_{pq})=\{1,2,\dots,p-1\} . In addition to the largest gap, we now also know the second largest gap of \Phi_{pq} , denoted by g_{2}(\Phi_{pq}) . This result is due to Cafure and Cesaratto [ 3 ] and it says that g_{2}(\Phi_{pq})=\max(r-1,p-r-1) , where r is the remainder of q on division by p . Finally, we mention what is known about the gaps of general cyclotomic polynomials \Phi_{n} . It is clear the the situation here is much more challenging than in the binary case we have been discussing above. Nevertheless, Al-Kateeb, et al, [ 1 ] were able to determine the largest gap of \Phi_{n} for n satisfying certain constraints. First, they note that if n_{0}=\prod_{p\mid n,p\geq 3}p is an “odd squarefree kernel” of n , then g_{1}(\Phi_{n})=\frac{n}{n_{0}}g_{1}(\Phi_{n_{0}}) . (Note that this applies to our case n_{0}=pq .) So the problem reduces to the study of gaps of \Phi_{n} for squarefree odd integers n . For such n , they showed that if the largest prime factor q of n satisfies q>\sqrt{n} , then g_{1}(\Phi_{n})=\varphi(n/q) , where \varphi is the Euler’s totient function. Henceforth we shall assume that integers q>p\geq 3 are coprime, but not necessarily prime numbers. We will work in the more general setting of binary inclusion-exclusion polynomials which are defined as quotients (1) Q_{\{p,q\}}(x)\coloneq\frac{(1-x^{pq})(1-x)}{(1-x^{p})(1-x^{q})}. It is easy to verify (see [ 2 ] for an introduction to inclusion-exclusion polynomials) that Q_{\{p,q\}}(x) reduces to a polynomial of degree \varphi(p,q)\coloneq(p-1)(q-1) , and we write Q_{\{p,q\}}(x)=\sum_{0\leq m\leq\varphi(p,q)}a_{m}x^{m}\qquad[a_{m}=a_{m}(p,q)]. When the pair \{p,q\} is a pair of prime numbers, polynomial Q_{\{p,q\}} is better known as the cyclotomic polynomial \Phi_{pq} . In particular, our gap results for this larger class of polynomials apply to the subclass of cyclotomic polynomials \Phi_{pq} . From the definition ( 1 ) and the fact that the degree of Q_{\{p,q\}} is \varphi(p,q) , it follows that (2) Q_{\{p,q\}}(x)\equiv(1-x)\sum_{i,j\geq 0}x^{iq+jp}\pmod{x^{\varphi(p,q)+1}}. Two things are now clear. First, is that each coefficient a_{m} takes on one of three possible values, 0 or \pm 1 . Second, is that it is all about integers representable as linear combinations of p and q with nonnegative integer coefficients, (3) \langle p,q\rangle\coloneq\{\,iq+jp\mid i,j\geq 0\,\}. Such a structure is called a numerical semigroup of embedding dimension two (see, for example [ 7 , §7] )—we took the liberty of abbreviating this to “binary semigroup” in our title. In view of ( 2 ), of crucial importance to us is the interesting part of \langle p,q\rangle , namely S(p,q)\coloneq\langle p,q\rangle\cap[0,(p-1)(q-1)]. We say interesting, because the largest integer not in \langle p,q\rangle is pq-p-q (see [ 7 , §2.1] ). The total number of integers in [0,(p-1)(q-1)] missing from S(p,q) is \vartheta\coloneq\varphi(p,q)/2 (see [ 7 , §5.1] ), the largest of which is pq-p-q , and the number of integers in S(p,q) is \vartheta+1 . We ought to comment that, unfortunately, we encounter here a bit of a notational conflict. The terms “gap” as well as “nongap” are also used in the context of these semigroups—the elements of \langle p,q\rangle are the nongaps and the missing integers are the gaps. We avoid this conflict by using the terms representable and nonrepresentable instead. It readily follows from ( 2 ) that the gaps of Q_{\{p,q\}} correspond to blocks of consecutive representable integers and blocks of consecutive nonrepresentable integers in [0,\varphi(p,q)] . More precisely (see Section 4 for details), by a block we mean two or more of consecutive integers of the same type, and the corresponding gap equals to the length of the block. Let us list the elements of S(p,q) in the increasing order: \ell_{0}<\ell_{1}<\dots<\ell_{\vartheta} , so that \ell_{0}=0,\,\ell_{1}=p,\,\dots,\,\ell_{\vartheta}=(p-1)(q-1) , and do the same for nonrepresentables: n_{1}<n_{2}<\dots<n_{\vartheta} , so that n_{1}=1,\,n_{2}=2,\,\dots,\,n_{\vartheta}=pq-p-q . Then block lengths are given by various values of \ell_{j+1}-\ell_{j}-1>0 and n_{j+1}-n_{j}-1>0 , and the preceding assertion is that G(Q_{\{p,q\}})=\{\,\ell_{j+1}-\ell_{j}-1>0\,\}\cup\{\,n_{j+1}-n_{j}-1>0\,\}. So the problem of understanding the gapset of polynomials Q_{\{p,q\}} comes to the same thing as the problem of understanding the sets (4) S_{\Delta}(p,q)\coloneq\{\ell_{j+1}-\ell_{j}\}\quad\text{and}\quad N_{\Delta}(p,q)\coloneq\{n_{j+1}-n_{j}\}, an interesting problem in its own right. We

Read the complete text