论文标题
具有非零恒定项的二进制副本多项式的枚举算法
An Enumeration Algorithm for Binary Coprime Polynomials with Nonzero Constant Term
论文作者
论文摘要
我们解决了在$ \ f_2 $上的副本多项式对的枚举，在$ \ f_2 $中，这两个多项式都有非零的常数项，这是由于通过细胞自动机对正交拉丁正方形的构建而动机。为此，我们利用了本杰明和贝内特在企业对和非派遣对之间的培养，这基于迪尔库（Dilcue）算法所访问的商序列（即欧几里得的算法向后运行）。这使我们能够分为三个部分，即：（1）常数术语，（2）度序列和（3）中间项的序列的列表和计数。对于（1），我们表明，常数术语的序列形成了常规语言，并使用代数语言理论的经典结果来计算它们。关于（2），我们指出，学位的序列对应于自然数的组成，它们具有简单的组合描述。最后，我们证明（3）可以自由选择中间术语。将这三个肥胖汇总在一起，我们设计了一种组合算法来列举给定程度的所有此类副本对，并提出了其计数公式的替代推导。
We address the enumeration of coprime polynomial pairs over $\F_2$ where both polynomials have a nonzero constant term, motivated by the construction of orthogonal Latin squares via cellular automata. To this end, we leverage on Benjamin and Bennett's bijection between coprime and non-coprime pairs, which is based on the sequences of quotients visited by dilcuE's algorithm (i.e. Euclid's algorithm ran backward). This allows us to break our analysis of the quotients in three parts, namely the enumeration and count of: (1) sequences of constant terms, (2) sequences of degrees, and (3) sequences of intermediate terms. For (1), we show that the sequences of constant terms form a regular language, and use classic results from algebraic language theory to count them. Concerning (2), we remark that the sequences of degrees correspond to compositions of natural numbers, which have a simple combinatorial description. Finally, we show that for (3) the intermediate terms can be freely chosen. Putting these three obeservations together, we devise a combinatorial algorithm to enumerate all such coprime pairs of a given degree, and present an alternative derivation of their counting formula.
