论文标题
在算法上查找p订购
On algorithms to find p-ordering
论文作者
论文摘要
Manjul Bhargava（在他的博士学位论文中）引入了Prime P的P级概念，以在整数的任意子集上开发一般的阶乘功能。 P阶的这种概念提供了多项式模型素数的表示，并已用于证明根集Modulo Prime Powers的属性。我们专注于在给定P级，指数k和整数模量p^k的子集的复杂性上。 我们的第一个算法给出了时间O（nk \ log P）的一组n尺寸n的p顺序，其中集合被视为模块p^k。可以使用代表根的概念简洁地表示模量（Panayi，PhD论文，1995； Dwivedi et.al，Issac，2019年）；一个自然的问题是，鉴于这种简洁的表示，我们可以找到更有效的p顺序。我们的第二个算法确切地达到，我们在时间O（d^2k \ log p + p + nk \ log p + nd）中给出了p顺序，其中d是简洁表示的大小，n是p订购的必需长度。我们做出的另一个贡献是计算k小时的质量p^k的根系结构。根集的数量已在先前的工作中给出（Dearden and Metzger，Eur。J.Comb。，1997; Maulick，J。Comb。理论，Ser。A，2001），我们明确描述了P^2，p^3和p^4的所有根集。
The concept of p-ordering for a prime p was introduced by Manjul Bhargava (in his PhD thesis) to develop a generalized factorial function over an arbitrary subset of integers. This notion of p-ordering provides a representation of polynomials modulo prime powers, and has been used to prove properties of roots sets modulo prime powers. We focus on the complexity of finding a p-ordering given a prime p, an exponent k and a subset of integers modulo p^k. Our first algorithm gives a p-ordering for set of size n in time O(nk\log p), where set is considered modulo p^k. The subsets modulo p^k can be represented succinctly using the notion of representative roots (Panayi, PhD Thesis, 1995; Dwivedi et.al, ISSAC, 2019); a natural question would be, can we find a p-ordering more efficiently given this succinct representation. Our second algorithm achieves precisely that, we give a p-ordering in time O(d^2k\log p + nk \log p + nd), where d is the size of the succinct representation and n is the required length of the p-ordering. Another contribution that we make is to compute the structure of roots sets for prime powers p^k, when k is small. The number of root sets have been given in the previous work (Dearden and Metzger, Eur. J. Comb., 1997; Maulick, J. Comb. Theory, Ser. A, 2001), we explicitly describe all the root sets for p^2, p^3 and p^4.
