ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let pp and tt be fixed, and let f∈Z[x1]f\in\mathbb{Z}[x_1] be an input tt-nomial, meaning a univariate integer polynomial with at most tt monomial terms. Root-counting conjecture. There is a polynomial-time algorithm that counts the roots of ff in Qp\mathbb{Q}_p. This conjecture proposes a tractable algorithm for root counting over pp-adic fields when both the prime and the number of monomial terms are fixed. The paper establishes polynomial-time algorithms for related problems for trinomials and shows a complexity barrier for tetranomials with fixed pp; counting points on trinomial curves over Fp\mathbb{F}_p in time log⁡O(1)(pd)\log^{O(1)}(pd) is noted as a challenging open question.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.