3
$\begingroup$

$\newcommand\S{\mathcal S}$ Let $p$ be a prime, and suppose that $0.9(p-1)<q<p-1$. Suppose, furthermore, that $H,B,T\in\mathbb F_p[x]$ satisfy $\max\{\deg H,\deg T\}\le q-1$ and $\deg B\le p-1-q$. What can be said about $B$ given that the polynomial $$ \S(x) := x^p H(x) + x^q B(x) + T(x) $$ is fully reducible (splits completely into linear factors)? Is it true that for any $B$ there exist $H$ and $T$ such that $\S$ is fully reducible? What is the set of all those polynomials $B$ for which $H$ and $T$ can be found so that $\S$ is fully reducible? Is there any reasonably strong condition that $B$ must satisfy in order for such $H$ and $T$ to exist?

As an example, if $B$ is the zero polynomial, then one can take $H(x)=1$ and $T(x)=-2x^{\frac{p+1}2}+x$ to get $$ \S(x)=x^p-2x^{\frac{p+1}2}+x=(x^{\frac{p-1}2}-1)^2x $$
which, of course, is fully reducible.

Improve this question
$\endgroup$
3
  • $\begingroup$ Sorry, I am probably confused and if so forgive me for what is likely a dumb remark, but for x\in \F_p you may replace the x^p term by simply x, and then you are asking that x^q B(x) + (x H(x) + T(x)) have q + \deg B roots mod p, i.e. you are asking for conditions on the leading \deg B (< 0.1 (p-1) ) coefficients of a polynomial over \F_p (of degree < p) of the form const * \prod_{\alpha\in S} (x - \alpha), where S\subseteq \F_p. [This recovers the 2^p vs. p^{0.1 p} comparison, of course.] It would be particularly nice if \deg B = p-1-q, in which case up to translation you’d have x^{p-1} - 1. $\endgroup$
    – alpoge
    Commented May 3, 2019 at 21:32
  • $\begingroup$ @alpoge: Replacing $x^p$ with $x$, you change the polynomial. The new polynomial will have the same roots as the original one, but the multiplicities can be affected, and full reducibility is not necessarily preserved (consider $x^{p-1}(x-1)$). $\endgroup$
    – Seva
    Commented May 4, 2019 at 6:30
  • $\begingroup$ Ah! I tacitly assumed the discriminant was nonzero when I saw split completely (I’m not sure why). Alas! $\endgroup$
    – alpoge
    Commented May 4, 2019 at 6:53

1 Answer 1

Reset to default
3
$\begingroup$

There are $p^{p-q}$ possible $B$'s, but for given $\deg H=k$ only $(p-1)\binom{p+k-1}k$ fully reducible polynomials of degree $p+k$. This is at most exponential in $p$, while $p^{p-q}$ for $q\sim 0.99 p$ is super exponential. Therefore most $B$'s are not realized.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the reply - but what I really need is a strong necessary condition for realizability, not just the mere fact that a typical $B$ is not realized. $\endgroup$
    – Seva
    Commented May 3, 2019 at 15:52
  • 1
    $\begingroup$ you mean explicit algebraic condition? If the polynomial $f$ is fully reducible then it divides $f'(x^p-x)$, maybe this helps somehow but I am not sure $\endgroup$
    – Fedor Petrov
    Commented May 3, 2019 at 21:34
  • $\begingroup$ Yes, I'd like to have a sort of algebraic condition; maybe, something about the coefficients of $B(x)$. Thanks for the observation about $f'(x^p-x)$, I'll check to see if it helps. $\endgroup$
    – Seva
    Commented May 4, 2019 at 6:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .