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

Question

我正在寻找一种方法来使用 GAP 系统找到非负整数上线性丢番图方程的解。明确地说，我有一个正整数列表 L，其中每个正整数都存在线性丢番图方程 s = 11*a + 7*b 的解，使得 a 和 b 是非负整数.我想要 GAP 系统 return L 的每个元素 s 对应于上述解决方案的有序对 [a, b]。

我已经熟悉 GAP 系统中的命令 SolutionIntMat；然而，这只会产生线性丢番图方程s = 11*a + 7*b的一些解。特别是，系数 a 和 b 之一可能（而且更有可能）为负。例如，当我对线性丢番图方程 75 = 11*a + 7*b.

使用上述命令时，我得到了解决方案 [-375, 600]

对于其他上下文，此查询在处理由广义算术序列生成的数值半群时出现。使用命令 LoadPackage("numericalsgps"); 来实现对此类对象的计算。例如，如果 S := NumericalSemigroup(11, 29, 36, 43, 50, 57, 64, 71);，那么除了 11 之外的每个 S 的最小生成器对于某个整数 i in [1..7] 都是 2*11 + 7*i 的形式。可以向 GAP 系统询问 SmallElements(S);，GAP 系统将 return S 到 FrobeniusNumber(S) + 1 的所有元素。显然，对于某些非负整数 a 和 b，S 的每个元素都具有 11*a + 7*b 形式；我想研究出现什么系数 a 和 b。其实答案是已知的（参见this paper的命题2.5）；我只是想了解证明背后的直觉。

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

Answer 1

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

您或许可以在此设置中使用包 numericalsgps 中的 Factorizations。它在内部重写 RestrictedPartitions 的输出。例如，在您的示例中，您可以通过键入 List(SmallElements(S), x->[x,Factorizations(x,S)]) 获得 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)；或者，如果您想要 S 的第一个元素，比如 200 个元素，请使用 S{[1..200]}.

您可能需要查看手册的 Chapter 9，尤其是 FactorizationsElementListWRTNumericalSemigroup。

希望对您有所帮助。

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

Linear Diophantine Equations with Restriction in the GAP System

diophantine

gap-system