Proportionally modular Diophantine inequality
Definition
Let \(a,b\) and \(c\) be positive integers. It is said that an expression is a proportionally modular Diophantine inequality if it is of the form \(ax ~ (mod ~ b) \le cx\). The integers \(a,b\) and \(c\) are called the factor, modulus and proportion, respectively.
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 = 4, b = 13\) and \(c = 2\) and define the proportionally modular Diophantine inequality \(4x ~ (mod ~ 13) \le 2x\). If \(x \in \{1,2,3\}\),
\[ 4x ~ (mod ~ 13) = 4x > 2x. \]
On the other hand, if \(x \ge 6\),
\[ 4x ~ (mod ~ 13) \le 12 \le 2x. \]
Furthermore, \(x = 0, x = 4\) and \(x = 5\) are also solutions. Therefore, the set of solutions is \(S(a,b,c) = \{0, 4, \rightarrow\}\).
Examples with GAP
The following examples are made with the package NumericalSgps in GAP.
\(\diamond\) Let \(a, b, c\) positive integers. Te function ProportionallyModularNumericalSemigroup returns the numerical semigroup generated by the proportionally modular Diophantine inequality \(ax ~ (mod ~ b) \le cx\).
gap> a := 14;
14
gap> b := 57;
57
gap> c := 6;
6
gap> S := ProportionallyModularNumericalSemigroup(a,b,c);
<Proportionally modular numerical semigroup satisfying 14x mod 57 <= 6x >The function SmallElements returns a list with the left elements and the conductor of the numerical semigroup.
gap> SmallElements(S);
[ 0, 5, 6, 7, 9 ]Therefore, the set of solutions of \(14x ~ (mod ~ 57) \le 6x\) is \(S = \{0, 5, 6, 7, 9, \rightarrow\}\).
\(\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 >If we use the function SmallElements,
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.