WOLFRAM

Wolfram 语言与系统参考资料中心
丢番图多项式系统

丢番图多项式系统

介绍多变量非线性系统
线性系统选项
单变量系统参考文献
双变量系统

介绍

丢番图多项式系统 是由形如

的多项式方程和不等式结合使用逻辑运算符和量词

等所构建的表达式，其中变量代表整数.

在 或 内部出现变量 ， 称为约束出现，任何其它情况下 的出现都称为一个自由出现. 如果多项式系统含有变量 的一个自由出现，则变量 被称作该系统的自由变量. 如果一个丢番图多项式系统不含量词，则该系统为无量词系统. 决策问题是全部变量被存在性量化(existentially quantified)的系统，即一个形如

的系统，其中 代表 中的所有变量. 决策问题（1）等价于 True 或 False，取决于多项式方程和不等式 的无量词系统是否有整数解.

丢番图多项式系统的一个例子是

于1742年提出、至今仍未证实的歌德巴赫猜想 [1] 断言系统（2）等价于 True. 这表明 Wolfram 语言可能不能求解任意丢番图多项式系统. 事实上，马季亚谢维奇（Matiyasevich）关于希尔伯特第十问题的解 [2] 表明，不存在任何解法能够求解任意丢番图多项式系统，甚至对无量词系统或是决策问题也是如此. 尽管如此，Wolfram 语言函数 Reduce、Resolve 和 FindInstance 还是能够对丢番图系统中几个相当大的类别求解. 本教程将解释这些系统类别以及 Wolfram 语言对这些类别求解的方法. 这些方法按照被使用的次序来分别介绍. 本教程也将介绍影响这些方法的选项以及它们的作用.

线性系统

线性方程系统

线性丢番图方程组的合取（Conjunctions of linear Diophantine equations）对于任意数目的变量可解. Wolfram 语言使用一种基于计算厄米正交矩阵的方法，这种方法在 Wolfram 语言中通过 HermiteDecomposition 可直接使用. 结果可能含有新的不受限制的整数参数. 如果方程互相独立，参数个数等于变量个数与方程个数之差.

这个系统含有四个变量和两个独立方程，因此结果用两个整数参数的形式表示：
Wolfram Language code: Reduce[3a + 4b + 18c + 24d == 30 && 27a + 16b + 28c + 24d == 30, {a, b, c, d}, Integers]

Frobenius 方程

Frobenius 方程是形如

的方程，其中 为正整数， 为整数，解的坐标 要求是非负整数.

为了找到Frobenius 方程解的实例，Wolfram 语言使用的是一种基于 Frobenius 图中计算临界树 [11] 的快速算法. 该算法适用于 中的最小值不超过 MaxFrobeniusGraph 系统选项值（默认值为1,000,000）的情形. 其它时候将使用一种更一般的用于求解有界线性系统的方法. 函数 FrobeniusSolve 与 FrobeniusNumber 为求解 Frobenius 方程和计算 Frobenius 数提供了专业化的功能.

这里得到了一个 Frobenius 方程的解：
Wolfram Language code: FindInstance[123456 x + 234567 y + 345678 z + 456789 u + 567890 v + 678901 w + 789012 r + 890123 s + 901234 t == 123456789 && x ≥ 0 && y ≥ 0 && z ≥ 0 && u ≥ 0 && v ≥ 0 && w ≥ 0 && r ≥ 0 && s ≥ 0 && t ≥ 0, {x, y, z, u, v, w, r, s, t}, Integers]

有界线性方程和不等式系统

如果线性方程和不等式系统的一个实数解集是一个有界的多面体，则系统存在有限多的整数解. 为了找到这些解， Wolfram 语言使用下述步骤.

用户可以假设系统有这种形式： ，其中 为一个 整数矩阵， 为一个长度为 的整数向量， 为一个 整数矩阵，以及 为一个长度为 的整数向量. 首先，使用求解线性方程系统的方法找到一个整数向量 ，使得 以及一个 的整数矩阵 N，其各行生成 的零空间. 的整数解集等于 . 令 ，. 的整数解集等于 ，其中 为 的整数解集. 为提高找到集合 的效率，Wolfram 语言使用 LatticeReduce 简化 ，得到 . 注意到若 的各列线性相关，则 无解（否则会有无穷多的解，这与假设矛盾）. 因此可以假设 具有线性无关的列，因此 有 列. 令 . 格规约法（Lattice reduction technique）也用于在格点（lattice） 中寻找小型向量 . 令 满足 . 集合 可以由满足 的所有的 的集合 ，根据公式 计算得到.

为了得到集合 ，可以使用一种简单的递归算法. 该算法使用 LinearProgramming 得到第一个变量的边界，对于边界内部的每一个整数值 ，将第一个变量设定为 递归地调用自身. 该算法是在系统选项 BranchLinearDiophantine 设为 False 时使用. 在默认设置 True 时，使用的是一种结合了递归算法和分支定界 (branch and bound) 算法的混合算法. 在递归的每一层，递归在第一个变量的中间值继续（定义为单位立方体内实数解集的点集的投影）而对于实数解集的剩余部分，则使用分支定界算法来寻找其中的整数解. FindInstance 使用分支定界算法得到它所需要的 的单一元素.

有两种系统选项，BranchLinearDiophantine 和 LatticeReduceDiophantine 允许用户对使用何种算法进行控制. 在某些情况下，改变这些选项的值可以显著改善 Reduce 的效果.

这里在一个三角形内找到所有的整数点：
Wolfram Language code: Reduce[7 x + y ≥ 3 && 3 x - 33 y + 333 ≥ 0 && x < y, {x, y}, Integers]

Wolfram 语言只有在系统整数解的个数不超过系统选项DiscreteSolutionBound 的值的 次幂时才将解显式地列出，其中 为方程组的解的格点（solution lattice）的维数，也是系统选项 ExhaustiveSearchMaxPoints 的值的第二个元素.

这里 Reduce 没有给出显式解，因为它们的数目超过了默认设置为10000的限度：
Wolfram Language code: Reduce[x ≥ 0 && y ≥ 0 && x + y ≤ 200, {x, y}, Integers]
这里将系统选项 DiscreteSolutionBound 的值增大到1000：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> 1000}];
由于存在两个变量而没有方程，现在解的个数的限度为 ，因此 Reduce 可以将解显式列出：
Wolfram Language code: Reduce[x ≥ 0 && y ≥ 0 && x + y ≤ 200, {x, y}, Integers]//Length
这里将 DiscreteSolutionBound 重新设为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> 10}];

任意线性方程和不等式系统

线性丢番图方程和不等式的无量词系统对于任意数目的变量都是可解的. 该系统以析取范式（disjunctive normal form）也就是合取（conjunctions）的析取（disjunction）形式写出，并对每一个合取分别求解. 若一个合取只含有方程，则使用求解线性方程系统的方法. 若变量个数与方程个数之差最多为1，Wolfram 语言使用求解线性方程系统的方法来求解方程组，同时如果解中至多存在一个自由参数（一般情况如此），则将解代回到不等式中来决定参数的不等式限制条件. 对于线性丢番图方程和不等式的无量词系统的所有其它情形，Wolfram 语言采用 [3] 中介绍的算法，在处理有界变量上进行某些基于线性规划的改进. 结果中可能含有新的非负整数参数，且新参数的数目可能要大于变量的数目.

这个系统含有三个变量，然而要表示解集，将需要八个非负整数参数：
Wolfram Language code: Reduce[a + 2b - 3c == 4 && 3a - 2b + c ≥ 1, {a, b, c}, Integers]

单变量系统

单变量方程

为得到单变量方程的解 Wolfram 语言使用的方法是基于 [4] 中给出的算法的一种变体、并进行了 [5] 中所介绍的改进. 应用该算法能够得到整数解的多项式的次数可以大大高于实根隔离算法所能求解的多项式的次数，并且其自由项也可以比整数分解算法能够处理的自由项大得多.

这里 Reduce 得到了次数为100,000的稀疏多项式的整数解：
Wolfram Language code: poly = x^100000 + 1234 x^77777 - 2121 x^12345 + 7890 x^999 - x^11; freeterm = poly /. x -> 1234567; Timing[Reduce[poly - freeterm == 0, x, Integers]]
这个多项式的自由项有609,152位数，不容易分解：
Wolfram Language code: N[freeterm]
Wolfram Language code: TimeConstrained[FactorInteger[freeterm]//Timing, 1000]

单变量方程和不等式系统

单变量丢番图方程和不等式系统以析取范式写出，并且每一个合取都单独求解. 如果一个合取包含一个方程，则使用求解单变量方程的方法，并选择满足其余方程和不等式的解.

此处 Reduce 得到了 的整数解，并选择满足不等式 的解：
Wolfram Language code: Reduce[x^4 - 25x^2 == -144 && x^100001 - 27 x + 5 ≥ 0, x, Integers]

只包含不等式的合取在整个实数域内求解. 如果结果实数区间上的整数解的数目不超过系统选项 DiscreteSolutionBound 的值，则这些整数解将被显式给出. 该选项的默认值为10. 对于区间上整数解的数目过大的情况，这些解将被隐式表示.

双变量系统

二次方程

Wolfram 语言能够对于含有双变量的任意二次丢番图方程求解. 这种方程的一般形式为

若 ，其中 和 为线性多项式，则方程（1）等价于 ，求解线性丢番图方程的方法将被使用. 对于不可约多项式 ，所用算法及结果的形式取决于二次形式的行列式 . 该算法可能用到整数因式分解，因此结果的正确与否取决于 PrimeQ 所用的概率素性检验（probabilistic primality test）的正确性.

带有平方行列式（Square Determinant）的双曲型方程（Hyperbolic-Type Equations）

若 且 为整数，则 ，其中 和 为线性多项式，且 . 这种情况下，对于所有 的除数 ，方程（1）等价于线性系统 的析取. 每一个线性系统在有理数域内有一个解，因此方程（1）的整数解个数有限.

这是一个二元二次方程，其中 ：
Wolfram Language code: Reduce[1 + 12 x + 2 x^2 + 7 y + 5 x y + 2 y^2 == 0, {x, y}, Integers]

带有非平方行列式（Nonsquare Determinant）的双曲型方程（Hyperbolic-Type Equations）

若 且 非整数，则方程（1）为 Pell 型方程. 求解这类方程的方法自18世纪起就已提出，可以在 [6] 和 [7] 的基础之上构建（尽管这些书并没有对该算法给出一个完整的介绍）. 解集为空或者无穷，由出现在指数上的一个整数参数进行参数化.

Pell 方程是一个形如 的方程，其中 不是一个平方数. 带有小系数的 Pell 方程可以非常复杂：
Wolfram Language code: Reduce[x^2 - 61 y^2 == 1, {x, y}, Integers]
这里是 的一个 Pell 型方程的解：
Wolfram Language code: sol = Reduce[7 + 5 x + x^2 + 7 y + 3 x y + y^2 == 0, {x, y}, Integers]
尽管解是用无理数表示的，实际上它们是整数，正如所期望的那样：
Wolfram Language code: Simplify[sol /. C[1] -> 7]
Reduce 可以对由一个 Pell 型方程和给出变量简单边界的不等式组成的系统求解：
Wolfram Language code: Reduce[x ^ 2 - 3y ^ 2 == 22 && 0 ≤ y ≤ 1000000, {x, y}, Integers]

抛物型方程

如果 ，设 ，，且 . 由于 ，所以 和 为非零整数，且 . 则有

设 且 . 则方程 (1) 等价于

假设 . 若方程 (1) 存在整数解，则可得出 对 有整数解，于是 为两个线性多项式的乘积. 由于此处 不可约，所以方程 (1) 无整数解.

若 ，则方程 (2) 意味着

若模方程 (3) 对 无解，则方程 (1) 无整数解. (若 ，则模方程 (3) 有一解，.）否则对于模方程 (3) 的某个解 ，有 . 在方程 (2) 中进行 的替换，并对所得线性方程求关于 的解得到

注意到由于 满足模方程 (3)，(4) 中最后一项的相除给出一个整数结果. 由于 且 ，所以. 综合考虑方程 (4) 和 ，得到

因此，对于模方程 (3) 的每个解 ，抛物型方程 (1) 的全解由单参数的解族组成，由方程 (4) 和 (5) 给出，其中 是一个整数.

这里 Reduce 得到了抛物型二次方程的整数解：
Wolfram Language code: Reduce[x^2 - 2 x y + y^2 + 5 x - 7 y == 22, {x, y}, Integers]

椭圆型方程

若 ，方程 (1) 的解为一个椭圆上的整数点. 由于椭圆是一个有界集合，解集的个数一定是有限的. 找到整数点的一种显而易见的算法是对于有限的 的每一个可能整数值计算关于 的解. 然而这种做法对于较大的椭圆可能会非常慢而不建议采用. Wolfram 语言使用的是 [8] 中介绍的一种较快的算法.

这里 Reduce 找到了椭圆型二次方程的正整数解. 有大于 个可能的正整数值，因此那个显而易见的算法对该椭圆并不适用：
Wolfram Language code: Reduce[23x^2 + 17y^2 == 1693339429465935072912802926367922572800 && x > 0 && y > 0, {x, y}, Integers]

Thue 方程

Thue 方程是一个形如

的丢番图方程，其中 是一个次数 的不可约齐次形式.

Thue 方程的解的个数总是有限的. 原则上 Wolfram 语言能够解出任意 Thue 方程，尽管找到解所需的时间随着次数和系数大小的增加而迅速延长. 该算法最困难的部分是为解的尺寸计算出一个界限. Wolfram 语言使用一种基于 Baker–Wustholz定理的算法来找到这个界限 [9]. 如果在输入中含有对解提供适当界限的不等式，Wolfram 语言就可以更快地将解计算出来.

这里找到了一个三次Thue 方程的整数解：
Wolfram Language code: Reduce[x^3 - 4 x y^2 + y^3 == 1, {x, y}, Integers]//Timing
如果对 Reduce 给定一个界限来限制解的大小，对方程的求解会显著加快：
Wolfram Language code: Reduce[x^3 - 4 x y^2 + y^3 == 1 && -10 ^ 10 < x < 10 ^ 10, {x, y}, Integers]//Timing
这里 Reduce 找到了一个15次 Thue 方程的唯一解，其中 坐标至多为100位. 如果对解的尺寸不加限制，Reduce 不能在1000秒内完成：
Wolfram Language code: Reduce[x^15 - 4 x ^12y^3 + 7x^7y^8 - 2y^15 == 23058325506004605670097246320963935108919550 && -10 ^ 100 < x < 10 ^ 100, {x, y}, Integers]//Timing

多变量非线性系统

可用模筛法（Modular Sieve Method）求解的系统

Wolfram 语言使用的是模筛法的一种变体 (参见 [9]). 该方法可以证明：由于系统按整数 为模无解，则该系统无整数解. 否则，它可以找到一个小整数坐标的解，或是证明该系统在 和 之间的全部坐标内无整数解. 允许筛法测试的候选解的点的个数由系统选项 SieveMaxPoints 控制.

这个方程模2无解）：
Wolfram Language code: Reduce[-2 x^3 y^9 + 6 x^5 y^5 z^2 + 6 x^8 y^2 z^5 + 4 x^7 y^6 z^7 == 7, {x, y, z}, Integers]
这里 FindInstance 使用模筛法得到了一个小的解：
Wolfram Language code: FindInstance[9 x^6 y^8 z - 81 x^2 y^9 z - 5 x^9 y^5 z^5 + 2 x^6 y^2 z^9 == 1080, {x, y, z}, Integers]

方程数大于一的系统

如果一个丢番图多项式系统的方程数大于一，Wolfram 语言使用 GroebnerBasis 来试图将问题约化为一系列较简单的问题.

通过在有限多部分解上迭代可解的系统

Wolfram 语言试图求解依赖于最小数目的初始变量的 Gröbner 基的一个元素. 如果解的个数是有限的，则对于每一个解，Wolfram 语言将计算得到的值代入系统，并在所得到的新系统中试图求解剩余的变量.

这里第一个方程关于 和 有四对整数解. 对于每一对解，第二个方程变成了一个关于 的一元方程. 这四个一元方程共有两个整数解：
Wolfram Language code: Reduce[x^4 - x y + y^2 == 7 && z^4 - x z + y^2 + y == 2400, {x, y, z}, Integers]
这里第一个方程是一个具有一个解的 Thue 方程. 将 和 用由第一个方程得到的值代替后，第二个方程变成了一个 Pell 方程：
Wolfram Language code: Reduce[x^3 - 2 y^3 == 11 && z^2 - x y w^2 == 1 && z > 0 && w > 0, {x, y, z, w}, Integers]

带有线性-三角形 Gröbner 基的系统

这种试探法适用于带有形如

的 Gröbner 基的系统.

这种情况下，Wolfram 语言求解同余（congruences）系统

解由新的整数参数表示. 这些解被代入原始系统中的方程 和不等式，然后 Wolfram 语言尝试对所得到的系统求解新的参数.

这个系统约化为对一个同余和一个 Pell 方程的求解：
Wolfram Language code: Reduce[x^2 - 7 y^2 == 1 && 2 z == x^3 - 1 && t - 4 z^2 + y == 7 && x > 0 && y > 0, {x, y, z, t}, Integers]
这个系统约化为求解一个由两个同余以及关于每一个同余的解族的抛物型二次丢番图方程组成的系统.
Wolfram Language code: Reduce[3 z == x^2 - 2 x y && 2 t == x^3 + 96 z^2 - 1 && (x - 2 y)^2 - 3 x == 18, {x, y, z, t}, Integers]

平方和

Wolfram 语言能够运用 [10] 中介绍的算法，求解形如

的方程. 对于多元二次方程，Wolfram 语言试图找到一个仿射变换（affine transformation）来将方程化为 (2) 的形式. 为达到这一目的，Wolfram 语言使用的是一种基于 CholeskyDecomposition 的试探法的方法. 然而对于一些可用形式 (2) 表示的方程，这种方法也可能会失败.

这里解出了含有三个变量的平方和方程：
Wolfram Language code: Reduce[(x - 2 y + 3 z)^2 + (4 y + 5 z)^2 + z^2 == 14, {x, y, z}, Integers]

为了得到 (2) 的一个单一解，FindInstance 使用一种基于 [12] 的算法.

这里将一个1000位的整数分解为七个平方的和. 使用 N 是为了使打印出来的结果较小：
Wolfram Language code: SeedRandom[10];a = RandomInteger[{0, 10^10000}];N[s7 = FindInstance[x^2 + y^2 + z^2 + t^2 + u^2 + v^2 + w^2 == a, {x, y, z, t, u, v, w}, Integers]]//Timing
这里证明了所得到的分解是正确的：
Wolfram Language code: x ^ 2 + y ^ 2 + z ^ 2 + t ^ 2 + u ^ 2 + v ^ 2 + w ^ 2 - a /. s7

勾股方程（Pythagorean equation）

Wolfram 语言知道勾股方程的解

这里给出了该勾股方程的一般解：
Wolfram Language code: Reduce[x^2 + y^2 == z^2, {x, y, z}, Integers]

对于含有三个变量的二次方程，Mathematica 试图找到形如

的一种变换，将方程转化为勾股方程.

这个方程可以转化为勾股方程：
Wolfram Language code: Reduce[-4 x + 5 x^2 - 2 y + 4 x y + y^2 + 28 x z + 6 y z + 72 z^2 == 8, {x, y, z}, Integers]

带有可约化非常数部分的方程

如果一个方程的非常数项的和可因式分解，Wolfram 语言使用公式

将方程约化为次数较低的方程对的析取. 这种约化取决于找到 的全部除数的能力，因此结果的正确与否取决于 PrimeQ 所用的概率素性检验（probabilistic primality test）的正确性.

这个三次方程约化为12对二次和线性方程：
Wolfram Language code: Reduce[(x - 2 y + 3 z) x^2 - (x - 2 y + 3 z) y z == 18, {x, y, z}, Integers]

带有一个线性变量的方程

Wolfram 语言试图对形如

的丢番图系统，通过将其约化为

的方法来求解，其中 是不等式或 True 的合取.

求解系统 (3) 的第一部分使用的是求解方程数大于一个的系统的方法. 当系统 (3) 的第二部分能够解出时，Wolfram 语言要识别三种情况. 若 ，解由 和通过求解不等式 得到的对 的限制条件得到. 非线性不等式系统用 CylindricalDecomposition 来求解. 若对于一个整数常数 ，，则系统 (3) 的第二部分由 和通过求解同余 、然后对于同余的每一个解求解不等式 所得到的对 的限制条件联立给出. 若 不是常数，在 时 Wolfram 语言可以求解系统 (3) 的第二部分. 由于 Wolfram 语言在预处理阶段将所有方程进行因式分解， 和 可以被认为是互素的. 则有

其中 为整数，多项式 和 的系数为整数，且 . 若 为整数，则 为整数，由此得到 或 . 由于 ，故只有有限个整数 满足最后一个条件. 因此，系统 (3) 的第二部分的解能够从有限个候选解中选择.

另外，Wolfram 语言使用下述试探法来识别系统 (3) 无解的情形. 如果存在一个整数 使得 恒能被 整除，而 恒不被 整除，则系统 (3) 无解. 的候选对象通过计算在一些点处 值的 GCD 得到.

最后两种方法是在有限个点集上进行穷举搜索（exhaustive search）. 所允许的搜索点的数目由系统选项 SieveMaxPoints 控制.

这里约化为 (3) 的形式，其中 ：
Wolfram Language code: Reduce[x^3 - 7 x y + 5 y^4 - z == 3 && 2 x - y > 1, {x, y, z}, Integers]
这里约化为 (3) 的形式，其中 ：
Wolfram Language code: Reduce[x^3 - 2 x^2 y + 9 x y^4 - 3 z == 8, {x, y, z}, Integers]
这里约化为系统 (3) 在 的情形：
Wolfram Language code: Reduce[x^5 + 7 x - 271 + y (x^3 + 21 x^2 - 17) == 0, {x, y}, Integers]
这里 Reduce 识别出系统无解，原因是 恒能被5整除，而 恒不能被5整除：
Wolfram Language code: Reduce[(9 x^6 y^3 z^4 - 9 x^2 y^3 z^8 - 5 y^8 z^9 - 10) t + 7 - 5 x^4 y z^4 + 7 x^8 y^2 z^4 - 9 z^8 - 4 x^6 y z^8 == 0, {x, y, z, t}, Integers]

带有空集或有界实数解集的系统

如果一个丢番图多项式系统不能通过任何其它方法求解，Wolfram 语言将在实数上使用柱形代数分解 (CAD) 算法对系统求解. 如果系统无实数解，则很明显该系统无整数解. 如果实数解集有界，则整数解数目是有限的. 原则上讲，这种情形下所有的整数解都可以通过柱形分解找到. 也就是说，对于每一个柱形，对第一个坐标的所有可能整数值进行枚举，然后对于第一个坐标的每一个值，枚举第二个坐标的所有可能整数值，如此继续下去. 然而，对于大型有界解集，这种方法可能导致所试探的点的数目庞大. 鉴于此，Wolfram 语言有一个界限来在实数区间上对显式枚举整数解的数量加以限制. 对于实数解集无界或是界限巨大的系统，解是通过返回 CAD 和全体变量须为整数这样一个条件来隐式表示. 注意，对于多变量系统，这种隐式表示可能都不足以表明是否存在整数解. 根据马季亚谢维奇（Matiyasevich）关于希尔伯特第十问题的解 [2]，这种情况应该可以预见的.

此处 Reduce 列举了有界实数域里的所有整数解：
Wolfram Language code: Reduce[x ^ 5 + y ^ 2 + z ^ 3 - x y z == 8 && x ^ 2 + y ^ 2 ≤ 30, {x, y, z}, Integers]
此处 Reduce 返回隐式解：
Wolfram Language code: Reduce[x^2 ≤ 10^8 && y^3 == x^4 - 2, {x, y}, Integers]
设置 DiscreteSolutionBound->Infinity 使得 Reduce 显式地列举任意有界集合的整数解：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> ∞}]; Reduce[x^2 ≤ 10^8 && y^3 == x^4 - 2, {x, y}, Integers]//Timing
这里将 DiscreteSolutionBound 重新设置为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> 10}];
此处模筛法表明在 上无解. 增加不等式来消去这个立方体后，Reduce 认识到这个方程在任何位置都无解：
Wolfram Language code: Reduce[9 x^2 y^2 + 7 x^2 z^2 + 5 y^2 z^2 == x y z + 10, {x, y, z}, Integers]

形如 的方程

Mathematica 尝试将形如

的丢番图系统，约化为

来求解，其中 是不等式或者 True 的合取.

所得到的系统 (4) 可能会也可能不会被较容易地解出. 能够以任意次数迭代应用这种变换的系统是存在的，因此 Wolfram 语言使用一种迭代界限（recursion bound）来确保这种试探法能够终止.

这里变换为无实数解的系统 (4) 的形式：
Wolfram Language code: Reduce[-x^2 + y + x y + x z == 0 && x > 0 && y > 0 && z > 0, {x, y, z}, Integers]
此处通过三次变换迭代后所得到的系统 (4) 有一个可化简的非常数部分：
Wolfram Language code: Reduce[x^3 - 2 x y^2 + 20 x y + y == 5, {x, y}, Integers]

能够通过穷举搜索求解的系统

对于所有变量都有明确的上下界的系统，Wolfram 语言通过穷举搜索来找到解. 搜索的界限通过系统选项 ExhaustiveSearchMaxPoints 的值设定. 选项的值应该是一对整数（默认值是 ）. 如果界限内整数点的个数不超过第一个整数，则使用穷举搜索，而不是除一元多项式求解外的其它任何方法. 其它情况时，如果界限内整数点的个数不超过第二个整数，则穷举搜索在所有其他方法都失败后使用.

这个带有有界变量值的超越丢番图方程（transcendental Diophantine equation）通过穷举搜索得到求解：
Wolfram Language code: Reduce[Sin[(π x y/2)]^2 == Gamma[21 x - 37 y] && 0 < x < 100 && 1 ≤ y ≤ 100, x, Integers]

选项

Wolfram 语言中用于求解丢番图多项式系统的函数有一系列的选项来控制其运行方式. 本教程对这些选项作一总结.

选项名称
默认值
GeneratedParametersC指定如何对新生成的用于表示解的参数命名

影响丢番图多项式系统的行为的 Reduce 选项.

GeneratedParameters

为表示某些丢番图系统的无穷多个解，Reduce 需要引入新的整数参数. 新参数的名字通过选项 GeneratedParameters 设定. 在设置为 GeneratedParameters->f 时，新参数被命名为 f[1], f[2], … .

默认设置时，由 Reduce 生成的新参数被命名为 C[1], C[2], … ：
Wolfram Language code: Reduce[x + y + z == 2 && x > y + 1, {x, y, z}, Integers]
选项 GeneratedParameters 允许用户选择个性化的参数名：
Wolfram Language code: Reduce[x + y + z == 2 && x > y + 1, {x, y, z}, Integers, GeneratedParameters -> (Subscript[k, #]&)]

系统选项的 ReduceOptions 组

这里是 ReduceOptions 组中的系统选项，这些选项可能影响到用于丢番图多项式系统的 Reduce、Resolve 和 FindInstance 的行为. 这些选项可以用如下方式设置

SetSystemOptions["ReduceOptions"->{"option name"->value}].
选项名称
默认值
"BranchLinearDiophantine"TrueReduce 是否使用分定支界型算法来计算线性丢番图不等式有界系统的解
"DiscreteSolutionBound"10在实数区间上明确列出整数解的个数的界限
"ExhaustiveSearchMaxPoints"{1000,10000}用于确定在使用所有其它解法之前及之后进行穷举搜索的变量界限内整数点数目的最大值
"ImplicitIntegerSolutions"Automatic当不能找到明确整数解时，Reduce 是否被允许返回带有 Element 条件的实解
"LatticeReduceDiophantine"True是否使用 LatticeReduce 对线性丢番图不等式的有界系统进行预处理
"MaxFrobeniusGraph"1000000Frobenius 方程中，最小系数使 FindInstance 对 Frobenius 图中的临界树进行计算的最大值
"SieveMaxPoints"{10000,1000000}用于确定使用模筛法在所有其他解法前后求解系统的点数的最大值

影响丢番图多项式系统中的 Reduce、Resolve 和 FindInstance 的行为的 ReduceOptions 组选项.

BranchLinearDiophantine

系统选项 BranchLinearDiophantine 的值设定在求解有界线性系统的最后一步中使用算法的何种变体. 在默认设置 "BranchLinearDiophantine"->False 下，使用一种简单的递归枚举法. 在设置 "BranchLinearDiophantine"->True 下，Reduce 使用一种结合了分定支界型算法和简单递归枚举法的混合方法.

这是在一个长且窄的四维单纯形上求整数点. 这里简单的递归枚举法比混合方法要明显快得多：
Wolfram Language code: a = 10000; SetSystemOptions["ReduceOptions" -> {"BranchLinearDiophantine" -> True}]; Reduce[a x + a y + a z - 3 (a - 1) t ≤ 3 a && a x + a y + a t - 3 (a - 1) z ≤ 3 a && a x + a z + a t - 3 (a - 1) y ≤ 3 a && a y + a z + a t - 3 (a - 1) x ≤ 3 a && x + y + z + t ≥ 1 && x < y && z < t, {x, y, z, t}, Integers]//Length//Timing
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"BranchLinearDiophantine" -> False}]; Reduce[a x + a y + a z - 3 (a - 1) t ≤ 3 a && a x + a y + a t - 3 (a - 1) z ≤ 3 a && a x + a z + a t - 3 (a - 1) y ≤ 3 a && a y + a z + a t - 3 (a - 1) x ≤ 3 a && x + y + z + t ≥ 1 && x < y && z < t, {x, y, z, t}, Integers]//Length//Timing
这里求解一个在 界定的单纯形内，由含有七个变量的两个随机生成的方程 与三个随机生成的不等式 组成的系统：
Wolfram Language code: SeedRandom[12]; A = Table[RandomInteger[{-1000, 1000}], {2}, {7}]; a = Table[RandomInteger[{-1000, 1000}], {2}]; B = Table[RandomInteger[{-1000, 1000}], {3}, {7}];b = Table[RandomInteger[{-1000, 1000}], {3}]; X = x /@ Range[7]; eqns = And@@Thread[A.X == a]; ineqs = And@@Thread[B.X ≥ b]; bds = And@@Thread[X ≥ 0] && Total[X] ≤ 100; SetSystemOptions["ReduceOptions" -> {"BranchLinearDiophantine" -> True}]; Reduce[eqns && ineqs && bds, X, Integers]//Timing
对于这个系统，使用非默认的简单递归方法较快：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"BranchLinearDiophantine" -> False}]; Reduce[eqns && ineqs && bds, X, Integers]//Timing

DiscreteSolutionBound

系统选项 DiscreteSolutionBound 的值对于整数解在实数区间 内是明确列出，还是以 的形式隐式表示进行设定. 设置为 DiscreteSolutionBound->n 时，若数目不超过 n，给定实数区间内的整数解将明确列出. 该选项的默认值为10.

在实数区间 内有10个整数. Reduce 将这些值明确写出：
Wolfram Language code: Reduce[0 ≤ x^3 < 1000, Integers]
在实数区间 内有11个整数. Reduce 将它们隐式表示：
Wolfram Language code: Reduce[0 ≤ x^3 < 1001, Integers]
这里将 DiscreteSolutionBound 增至11：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> 11}];
现在 Reduce 将解明确表示出来：
Wolfram Language code: Reduce[0 ≤ x^3 < 1001, Integers]

DiscreteSolutionBound 的值同时影响着求解有界线性方程组及其他具有有限多个解的丢番图系统. 在您需要在有界区域内对数目庞大的解进行显式枚举时，将 DiscreteSolutionBound 设置为 Infinity.

在默认设置 DiscreteSolutionBound 下，Reduce 求得解集的参数化描述：
Wolfram Language code: a = 1000000; SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> 10}]; Reduce[a x + a y + a z - 3 (a - 1) t ≤ 3 a && a x + a y + a t - 3 (a - 1) z ≤ 3 a && a x + a z + a t - 3 (a - 1) y ≤ 3 a && a y + a z + a t - 3 (a - 1) x ≤ 3 a && x + y + z + t ≥ 1 && x < y && z < t, {x, y, z, t}, Integers]//Timing
设置 DiscreteSolutionBound->Infinity 使得 Reduce 对解进行显式枚举. 在这个例子中，得到解的显式枚举较快：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> Infinity}]; Reduce[a x + a y + a z - 3 (a - 1) t ≤ 3 a && a x + a y + a t - 3 (a - 1) z ≤ 3 a && a x + a z + a t - 3 (a - 1) y ≤ 3 a && a y + a z + a t - 3 (a - 1) x ≤ 3 a && x + y + z + t ≥ 1 && x < y && z < t, {x, y, z, t}, Integers]//Length//Timing
这里将 DiscreteSolutionBound 重新设置为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"DiscreteSolutionBound" -> 10}];

ExhaustiveSearchMaxPoints

系统选项 ExhaustiveSearchMaxPoints 设定穷举搜索法所用的搜索点的最大数目. 选项值应该是一对整数（默认值为 ）. 如果界限内的整数点的个数不超过第一个整数，则使用穷举搜索，而不是其它任何方法（一元多项式的求解除外）. 其它情况时，如果界限内整数点的个数不超过第二个整数，则在所有其他方法都失败后使用穷举搜索.

在默认设置 ExhaustiveSearchMaxPoints 时，Reduce 不能对这个方程求解：
Wolfram Language code: Reduce[Binomial[x, y] == Gamma[x + y] && 1 ≤ x ≤ 200 && 1 ≤ y ≤ 200, {x, y}, Integers]
这里将 ExhaustiveSearchMaxPoints 的第二个元素的值增至 ：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {1000, 100000}}];
现在 Reduce 可以对该方程求解：
Wolfram Language code: Reduce[Binomial[x, y] == Gamma[x + y] && 1 ≤ x ≤ 200 && 1 ≤ y ≤ 200, {x, y}, Integers]
在默认设置 ExhaustiveSearchMaxPoints 时，Reduce 对以下系统使用的是求解 Pell 方程所用的方法：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {1000, 10000}}];Reduce[x^2 - 2 y^2 == 1 && 1 ≤ x ≤ 1000 && 1 ≤ y ≤ 1000, {x, y}, Integers]//Timing
将 ExhaustiveSearchMaxPoints 的第一个元素的值增至 ，使得 Reduce 首先进行穷举搜索. 此例中这种搜索比 Pell 方程解法慢了很多：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {10^6, 10^6}}]; Reduce[x^2 - 2 y^2 == 1 && 1 ≤ x ≤ 1000 && 1 ≤ y ≤ 1000, {x, y}, Integers]//Timing
对于下面这个方程，Pell 方程解法比穷举搜索慢：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {1000, 10000}}]; Reduce[x^2 - 21 y^2 == 2004 && 1 ≤ x ≤ 100 && 1 ≤ y ≤ 100, {x, y}, Integers]//Timing
这里穷举搜索更快一些：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {10000, 10000}}];Reduce[x^2 - 21 y^2 == 2004 && 1 ≤ x ≤ 100 && 1 ≤ y ≤ 100, {x, y}, Integers]//Timing
这里将 ExhaustiveSearchMaxPoints 重新设定为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {1000, 10000}}];

ImplicitIntegerSolutions

系统选项 DiscreteSolutionBound 的值指定在实数区间 上的整数解是显式枚举，还是隐式表示为 . 在设置 DiscreteSolutionBound->n 时，在已知实数区间上的整数解如果数目不超过 n，则被显式枚举. 选项的默认值为10.

在默认情况下，当 Reduce 不能找到显式整数解时，它将返回具有 Element 条件的实数解：
Wolfram Language code: Reduce[x^2 - y^3 - x y == 2, {x, y}, Integers]
在设置 ImplictIntegerSolutions->False 时，Reduce 仅允许丢番图问题的显式解：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ImplicitIntegerSolutions" -> False}]; Reduce[x^2 - y^3 - x y == 2, {x, y}, Integers]
在默认设置 ImplictIntegerSolutions->Automatic 下，对于递归生成的丢番图子问题，Reduce 仅允许显式解：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ImplicitIntegerSolutions" -> Automatic}]; Reduce[x^2 - y^3 - x y == 2 && Mod[x + y, 3] == 1, {x, y}, Integers]
设置 ImplictIntegerSolutions->True 使得 Reduce 接受递归生成的丢番图子问题的隐式解：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ImplicitIntegerSolutions" -> True}]; Reduce[x^2 - y^3 - x y == 2 && Mod[x + y, 3] == 1, {x, y}, Integers]
这里将 ImplicitIntegerSolutions 重新设定为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"ImplicitIntegerSolutions" -> Automatic}];

LatticeReduceDiophantine

系统选项 LatticeReduceDiophantine 的值设定是否使用 LatticeReduce 对有界线性不等式系统进行预处理. 对于所描述的多面体在某些非坐标轴的直线上的投影比在坐标轴上的投影要小得多的不等式系统，LatticeReduce 的使用非常重要. 然而对于有些系统，LatticeReduce 的使用非但不能简化问题，反而会使难度显著增加.

这里在一个三角形内找到了仅有的两个整数点，该三角形在两个坐标轴上的投影的尺寸均大于 ，但在直线 上的投影为一：
Wolfram Language code: a = 10^4; Reduce[a x ≤ (a + 1) y && (a + 1) x ≥ (a + 2) y && 0 ≤ x ≤ a + 1, {x, y}, Integers]//Timing
这里将系统选项 LatticeReduceDiophantine 的值设为 False：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"LatticeReduceDiophantine" -> False}];
对于这个系统，非默认方法要慢得多，并且速度的差距随着 的增大而增大：
Wolfram Language code: Reduce[a x ≤ (a + 1) y && (a + 1) x ≥ (a + 2) y && 0 ≤ x ≤ a + 1, {x, y}, Integers]//Timing
下面的系统包含相对复杂的等式 的一个集合，同时包含简单不等式 的一个集合，将解限定在一个不很大的多面体内. 对于这类系统，使用 LatticeReduce 趋向于使时间增长：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"LatticeReduceDiophantine" -> True}]; SeedRandom[1]; B = Table[RandomInteger[{-1000, 1000}], {3}, {5}];b = Table[RandomInteger[{-1000, 1000}], {3}]; X = x /@ Range[5]; ineqs = And@@Thread[B.X ≥ b]; bds = And@@Thread[X ≥ 0] && Total[X] ≤ 10; Reduce[ineqs && bds, X, Integers]//Length//Timing
对于这个系统，非默认方法较快：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"LatticeReduceDiophantine" -> False}]; Reduce[ineqs && bds, X, Integers]//Length//Timing
以下重新设置 LatticeReduceDiophantine 为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"LatticeReduceDiophantine" -> True}];

MaxFrobeniusGraph

系统选项 MaxFrobeniusGraph 用于设定 Frobenius 方程中，最小系数使 FindInstance 使用基于计算 Frobenius 图中临界树 [11] 的算法的最大位数. 其它情况下，使用的是更一般的求解有界线性系统的方法. 与求解有界线性系统的一般方法不同，这种基于 Frobenius 图的计算的方法与变量数目几乎无关，因此对于存在很多变量的方程，这是一种较快的选择. 而另一方面，由于该方法要求存储一个具有最小系数大小的图，对于大型系数，可能会耗尽内存.

为了找到最小系数大于 的 Frobenius 方程的解，FindInstance 在默认情况下使用求解有界线性系统的一般方法. 对于这个例子而言，该方法相对较慢，但几乎不耗内存. 为了显示当前例子的内存用量，内核（kernel）被作了重新启动：
Wolfram Language code: SeedRandom[1]; A = Table[RandomInteger[{5 10^7, 10^8}], {25}]; X = x /@ Range[25]; FindInstance[A.X == 10 ^ 9 && And@@Thread[X ≥ 0], X, Integers]//Timing
Wolfram Language code: MaxMemoryUsed[]
这里将 MaxFrobeniusGraph 的值增至 ：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"MaxFrobeniusGraph" -> 10^8}];
现在 FindInstance 使用的是基于计算 Frobenius 图的方法. 它找到解的速度较快，但占用的内存也较多：
Wolfram Language code: FindInstance[A.X == 10 ^ 9 && And@@Thread[X ≥ 0], X, Integers]//Timing
Wolfram Language code: MaxMemoryUsed[]
这里将 MaxFrobeniusGraph 重新设为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"MaxFrobeniusGraph" -> 10^6}];

SieveMaxPoints

系统选项 SieveMaxPoints 设定的是模筛法及在带有一个线性变量的方程中所用的搜索的搜索点的最大数目. 选项的值是一个数对 . 在尝试一些较慢的解法之前，对涉及至多 个点进行搜索. 对于决策问题，将在所有其他方法失败之后，尝试对涉及至多 个点的另一种搜索. 该选项的默认值是10,000.

在 SieveMaxPoints 的默认设置下，FindInstance 不能得到第一个方程的解，也不能表明第二个方程无解：
Wolfram Language code: FindInstance[x^2 + 21 y^3 - 17 z^4 == 632, {x, y, z}, Integers]
Wolfram Language code: FindInstance[11 x^2 + 17 y^3 == 55, {x, y}, Integers]
将 SieveMaxPoints 的第二个元素增大至 ，使得 FindInstance 能够对问题求解：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"SieveMaxPoints" -> {10^4, 10^8}}]; FindInstance[x^2 + 21 y^3 - 17 z^4 == 632, {x, y, z}, Integers]
Wolfram Language code: FindInstance[11x ^ 2 + 17y ^ 3 == 55, {x, y}, Integers]
Reduce 对模筛法进行第二次调用，并增大点数的上限，这仅对决策问题有效：
Wolfram Language code: Reduce[11 x^2 + 17 y^3 == 55, {x, y}, Integers]
将 SieveMaxPoints 的第一个元素增加至 ，使得 Reduce 能够对问题进行完全求解：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"SieveMaxPoints" -> {10^7, 10^8}}]; Reduce[11 x^2 + 17 y^3 == 55, {x, y}, Integers]
这里将 SieveMaxPoints 重新设置为默认值：
Wolfram Language code: SetSystemOptions["ReduceOptions" -> {"SieveMaxPoints" -> {10000, 1000000}}];

参考文献

[1] Goldbach, C. Letter to L. Euler, June 7, 1742. http://mathworld.wolfram.com/GoldbachConjecture.html. [online version]
[2] Matiyasevich, Yu. V. "The Diophantineness of Enumerable Sets (Russian)" Dokl. Akad. Nauk SSSR 191 (1970): 279–282. English translation: Soviet Math. Dokl. 11 (1970): 354–358.
[3] Contejean, E. and H. Devie. "An Efficient Incremental Algorithm for Solving Systems of Linear Diophantine Equations." Information and Computation 113 (1994): 143–172.
[4] Cucker, F., P. Koiran, and S. Smale. "A Polynomial Time Algorithm for Diophantine Equations in One Variable." Journal of Symbolic Computation 27, no. 1 (1999): 21–30.
[5] Strzebonski, A. "An Improved Algorithm for Diophantine Equations in One Variable." Paper presented at the ACA 2002 Session on Symbolic-Numerical Methods in Computational Science, Volos, Greece. Notebook with the conference talk available at members.wolfram.com/adams.
[6] Dickson, L. E. History of the Theory of Numbers. Chelsea, 1952.
[7] Nagell, T. Introduction to Number Theory. Wiley, 1951.
[8] Hardy, K., J. B. Muskat and K. S. Williams. "A Deterministic Algorithm for Solving in Coprime Integers and ." Mathematics of Computation 55 (1990): 327–343.
[9] Smart, N. The Algorithmic Resolution of Diophantine Equations. Cambridge University Press, 1998.
[10] Bressoud, D. M. and S. Wagon. A Course in Computational Number Theory. Key College Publishing, 2000.
[11] Beihoffer, D. E., J. Hendry, A. Nijenhuis, and S. Wagon. "Faster Algorithms for Frobenius Numbers." to appear in The Electronic Journal of Combinatorics.
[12] Rabin, M. O. and J. O. Shallit. "Randomized Algorithms in Number Theory." Communications on Pure and Applied Mathematics 39 (1986): 239–256.