Modular Diophantine inequality
Definition
Let \(a\) and \(b\) be positive integers. It is said that an expression is a modular Diophantine inequality if it is of the form \(ax ~ (mod ~ b) \le x\). The integers \(a,b\) are called the factor and modulus respectively. An expression of the form \(ax ~ (mod ~ b) \le cx\) for some \(a,b,c\) positive integers are called proportionally modular Diophantine inequality.
It can be proven that the set of solutions,
\[ S(a,b,c) = \{ x \in \mathbb{N} ~ | ~ ax ~ (mod ~ b) \le cx\}, \]
is a numerical semigroup. If \(S\) is a numerical semigroup such that \(S = S(a,b,c)\) for some \(a,b,c\) positive integers with \(c \ne 1\), it is said that \(S\) is proportionally modular, and if \(c = 1\), then it is said that \(S\) is modular.
Examples
\(\circ\) Let \(a = 3, b = 8\) and define the modular Diophantine inequality \(3x ~ (mod ~ 8) \le x\). For \(x \in \{1, 2\}\),
\[ 3x ~ (mod ~ 9) = 3x > x. \]
On the other hand, if \(x \ge 8\),
\[ 3x ~ (mod ~ 9) \le 8 \le x. \]
Moreover, \(x \in S(3,8,1)\) for all \(x \in \{0, 3, 4, 6, 7\}\) and for \(x = 5\) the inequality does not hold. Therefore, the set of solutions is \(S(a,b,c) = \{0, 3, 4, 6, \rightarrow\}\).
Examples with GAP
The following example is made with the package NumericalSgps in GAP.
\(\diamond\) Let \(a, b\) positive integers. The function ModularNumericalSemigroup returns the numerical semigroup generated by the modular Diophantine inequality \(ax ~ (mod ~ b) \le x\).
gap> a := 6;
6
gap> b := 19;
19
gap> S := ModularNumericalSemigroup(a,b);
<Modular numerical semigroup satisfying 6x mod 19 <= x >The function SmallElements returns a list with the left elements and the conductor of the numerical semigroup.
gap> SmallElements(S);
[ 0, 7, 10, 11, 13 ]Then, the set of solutions of \(6x ~ (mod ~ 19) \le x\) is \(S = \{0, 7, 10, 11, 13, \rightarrow \}\).
References
https://gap-packages.github.io/ numericalsgps.