Finding roots of a bivariate polynomial 𝑓 (𝑥1, 𝑥2), over a prime field F𝑝 , is a fundamental question with a long history and several practical algorithms are now known. Effective algorithms for describing the roots modulo 𝑝𝑘 , 𝑘 ≥ 2, for any general bivariate polynomial, were unknown until the present paper. The main obstruction is lifting the singular F𝑝 roots to Z/𝑝𝑘 Z. Such roots may be numerous and behave unpredictably, i.e., they may or may not lift from Z/𝑝 𝑗 Z to Z/𝑝 𝑗+1Z.
We give the first algorithm to describe the roots of a bivariate polynomial over Z/𝑝𝑘 Z in a practical way. Notably, when the degree of the polynomial is constant, our algorithm runs in deterministic time which is polynomial in 𝑝 + 𝑘. This is a significant improvement over brute force, which would require exploring 𝑝2𝑘 possible values. Our method also gives the first efficient algorithms for the following problems (which were also open): (1) efficiently representing all the (possibly infinitely-many) 𝑝-adic roots, and (2) computing the underlying Igusa’s local zeta function. We also obtain a new, effective method to prove the rationality of this zeta function.
The concept of 𝑝-ordering for a prime 𝑝 was introduced by Manjul
Bhargava (in his PhD thesis) to develop a generalized factorial function over an
arbitrary subset of integers. This notion of 𝑝-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 𝑝-ordering
given a prime 𝑝, an exponent 𝑘 and a subset of integers modulo 𝑝𝑘 .
Our first algorithm gives a 𝑝-ordering for set of size 𝑛 in time ˜O (𝑛𝑘 log 𝑝), where set is considered modulo 𝑝𝑘 . The subsets modulo 𝑝𝑘 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 𝑝-ordering more efficiently given this succinct representation. Our second algorithm achieves precisely that, we give a 𝑝-ordering in time ˜O (𝑑2 𝑘 log 𝑝 + 𝑛𝑘 log 𝑝 + 𝑛𝑑), where 𝑑 is the size of the succinct representation and 𝑛 is the required length of the 𝑝- ordering. Another contribution that we make is to compute the structure of roots sets for prime powers 𝑝𝑘 , when 𝑘 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 𝑝2, 𝑝3 and 𝑝4.
We consider estimating the edge-probability matrix of a network generated from a graphon model when the full network is not observed—only some overlapping subgraphs are. We extend the neighbourhood smoothing (NBS) algorithm of Zhang et al. (2017) to this missing-data set-up and show experimentally that, for a wide range of graphons, the extended NBS algorithm achieves significantly smaller error rates than standard graphon estimation algorithms such as vanilla neighbourhood smoothing (NBS), universal singular value thresholding (USVT), blockmodel approximation, matrix completion, etc. We also show that the extended NBS algorithm is much more robust to missing data.