GAP系统中带约束的线性丢番图方程

Question

我正在寻找一种利用间隙系统来寻找非负整数上线性丢番图方程的解的方法。明确地，我有一个正整数的列表L，其中每个正整数都有一个线性丢番图方程s = 11*a + 7*b的解，使得a和b是非负整数。我希望每个元素s of L的GAP系统返回对应于上述解的有序对(S) [a, b]。

我已经熟悉了GAP系统中的命令SolutionIntMat；然而，这只产生了线性丢番图方程s = 11*a + 7*b的一些解。特别是，其中一个系数a和b是负的，这是可能的(而且更有可能)。例如，当我在线性丢番图方程[-375, 600]上使用上述命令时，我获得了解75 = 11*a + 7*b。

对于附加上下文，当处理由广义算术序列生成的数值半群时，就会出现此查询。使用命令LoadPackage("numericalsgps");实现这些对象的计算。例如，如果是S := NumericalSemigroup(11, 29, 36, 43, 50, 57, 64, 71);，那么除了11以外，S的每一个最小生成器都是一些整数i in [1..7]的形式2*11 + 7*i。可以要求SmallElements(S);的GAP系统，GAP系统将S的所有元素返回到FrobeniusNumber(S) + 1。显然，对于一些非负整数，S的每个元素都是11*a + 7*b形式的，a和b；我想研究一下a和b产生了哪些系数。事实上，答案是已知的。(本论文的命题2.5 )；我只是想了解证据背后的直觉。

提前感谢您的时间和考虑。

Answer 1

迪伦，谢谢你的查询和使用GAP和numericalsgps。

您可能可以在此设置中使用来自包Factorizations的numericalsgps。它在内部重写RestrictedPartitions的输出。例如，在您的示例中，您可以通过键入S来获得S的小元素的所有可能的“因式分解”。一个特别的例子：

gap> Factorizations(104,S);
[ [ 1, 0, 0, 1, 1, 0, 0, 0 ], [ 1, 0, 1, 0, 0, 1, 0, 0 ], 
  [ 1, 1, 0, 0, 0, 0, 1, 0 ], [ 3, 0, 0, 0, 0, 0, 0, 1 ] ]

如果您希望看到S元素的11和7的因式分解，那么您可以执行以下操作：

gap> FactorizationsIntegerWRTList(29,[11,7]);
[ [ 2, 1 ] ]

因此，对于所有最小的S生成程序，您将执行以下操作

gap> List(MinimalGenerators(S), g-> FactorizationsIntegerWRTList(g,[11,7]));
[ [ [ 1, 0 ] ], [ [ 2, 1 ] ], [ [ 2, 2 ] ], [ [ 2, 3 ] ], 
  [ [ 2, 4 ] ], [ [ 2, 5 ] ], [ [ 2, 6 ] ], [ [ 2, 7 ] ] ]

对于S的一组小元素，请尝试List(SmallElements(S), g-> FactorizationsIntegerWRTList(g,[11,7]))。如果您只想达到某个整数，只需将SmallElements(S)替换为Intersection([1..200], S)；或者如果您希望使用第一个元素，例如200，S元素，则使用S{[1..200]}。

您可能想看看手册的第九章，特别是FactorizationsElementListWRTNumericalSemigroup。

我希望这能帮到你。