Re: -- reducibility in K[x]

On Feb 18, 12:51 pm, quasi <qu...@xxxxxxxx> wrote:
On Mon, 18 Feb 2008 09:13:06 -0800 (PST), "Mariano Suárez-Alvarez"



<mariano.suarezalva...@xxxxxxxxx> wrote:

quasi wrote:
On Mon, 18 Feb 2008 07:54:24 -0800 (PST), Chip Eastham
<hardm...@xxxxxxxxx> wrote:

On Feb 16, 8:46 pm, quasi <qu...@xxxxxxxx> wrote:
I don't think anyone understood the point of my prior post, so in an
effort to clarify it, I'll restate the conjecture, but this time over
an arbitrary field.

Let K be a field.

Consider the following boolean functions on K[x].

For f in K[x], define

is_red(f) = true if f is reducible in K[x], false otherwise.

has_root(f) = true if f has a root in K, false otherwise.

If deg(f) < 4, then is_red(f) = has_root(f).

In general, has_root(f) => is_red(f), but not necessarily conversely.

Now suppose, for a given field K, the function has_root has been
provided. In other words, for each f in K[x], we can determine whether
of not f has a root in K. Then for each f in K[x], we can also
determine whether or not f is reducible. This is done by first using
the method of undetermined coefficients on the potential factors of f,
followed by using the Grobner basis algorithm to produce univariate
conditions on the undetermined coefficients.

Thus, irreducibility boils down to root testing -- if you can do one,
you can do the other.

Hence, it suffices to consider root testing.

Assume the field operations are effective. In other words, given
elements of K, we can add, subtract, multiply, divide (by nonzero
elements), and determine whether or not an element is 0.

But for root testing that's clearly not enough.

Consider the polynomials of the form x^n - c, where c is in K. Testing
such a polynomial for a root in K is equivalent to being able to
answer the question "Is c an n'th power of an element of K?".

Thus, for c in K, n in N, define the boolean function is_pow by

is_pow(c,n) = true if c is an n'th power of an element of K,
false otherwise

A first question is this ...

Given an arbitrary field K together with the following effective
operations and functions

arithmetic operations: +, - , *, /
is_zero
is_pow

is there a formula or algorithm based on the above which enables
evaluation of the function

has_root

?

My conjecture is "no".

But I intend to make a much stronger conjecture, so let's go on ...

Assume f is nonconstant, and let n = deg(f).

If n = 1, then f always has a root in K.

Next, suppose n = 2.

Thus, let f(x) = ax^2 + bx + c, where a,b,c in K and a =/= 0.

Then f has a root in K iff b^2 - 4ac is a square in K.

Thus, if we restrict to the case n = 2, having the function is_square
(a specialization of is_pow) is a necessary and sufficient condition
for having the function has_root.

Now consider n = 3 ...

I know of no analogue of the simple power test which works for n = 2.
I conjecture there is no such condition (that works for _all_ fields
K).

To make that precise, I need to clarify the acceptable form for such a
condition.

Let me start by identifying a condition which would _not_ be
acceptable:

Let f(x) = ax^3 + bx^2 + cx + d where a,b,c,d in K, and a =/= 0.

Then has_root(f) = true

iff

ax^3 + bx^2 + cx + d = 0 for some x in K.

Clearly the above condition is valid. However, allowing "solving" is
too strong, although, as a final result, that's what we hope to
achieve. We would like the condition to be based only on arithmetic
combinations of the coefficients, together with some simple boolean
operations (short of solving) such as subset membership (i.e. "is a
given element a square?").

Thus, let me try to identify more precisely the types of conditions
that _would_ qualify.

Certainly, we want the condition b^2 - 4ac is a square in K to qualify
(otherwise we're dead right at the start), therefore let's grant use
of the boolean function is_pow. The idea is to stingily grant only as
much as is needed. However, I have already conjectured that having
is_pow is not enough. Of course, I can't prove it's not enough --
that's why it's a conjecture. But in any case, as indicated, I intend
to make an even stronger conjecture (i.e. -- grant use of other
boolean functions), so let's keep going ...

This part is a little abstract, so may or not be easily understood,
however I'll do my best to transmit the idea ...

To say it as simply as possible, we are granting

effective membership testing for an arbitrary subset of K.

This idea generalizes power testing. To see this, let S_m be the set
of m'th powers of elements of K. Then is_pow can be used to determine
membership in S_m. But now we are granting more. For _any_ subset S of
K, we grant the boolean function is_mem, defined by

is_mem(x,S) = true if x is in S, false otherwise.

As an alternate way to describe it, we are granting characteristic
functions for _every_ subset of K.

I claim that's still not enough. More precisely, I conjecture ...

Conjecture (for n = 3):

There is no boolean expression P (quantifier free logical statement)
whose atoms have the form

is_mem(p_m(a,b,c,d),S_m)

for some rational functions p_1, ..., p_m and subsets S_1, ..., S_m of
K such that P = has_root(f).

The essence of my conjecture is that if you want to do root testing,
it's not enough to look at (and do subset membership testing on) any
finite set of rational functions of the coefficients. For degree 2 you
can get away with that, but not for any higher degrees.

quasi

Hi, quasi:

Judging by the prior post, I think you have in mind
fields of characteristic zero,

No -- fully general.

even though you've stated the conjecture/question more generally.

Note that for finite fields K, evaluating polynomial
f at each element of K does suffice to determine if
there is a root.

Sure, but that's a subclass of the class of all fields. I want a
criterion, if any, for the full class, based only on subset testing.

For the special case Q of the previous post, we have
the rational roots theorem, which limits root finding
to a finite number of possibilities (for any fixed
polynomial f).

Sure, but once again, using K = Q specializes to one field -- I want a
general condition that works for _all_ fields, or a proof that there
is none. Of course, I'm not going to let such a condition invoke the
right to solve equations directly -- only indirectly via subset
testing. If it that's not enough, and if that can be _proved_ that
it's not enough, then my conjecture is validated.

Therefore I think it essential to the precision of
your conjecture that you proscribe how boolean P
and its atoms are allowed to depend on polynomial f.

In a way that depends on the coefficients, _independent_ of the field.

In other words, the analogue of the criterion for degree 2.

Of course, for degree 1, there is always a root in K, so degree 1 is a
non-issue.

For degree 2, letting f(x) = ax^2 + bx + c, where a,b,c in K and a =/=
0, then

f has a root K iff b^2 - 4ac is a square in K.

This statement is not true, actually, in that generality:
Every element of F_2 is a square, and there are irreducible
polynomials of degree 2...

Hmmm ...

I guess I need characteristic not equal to 2.

To avoid such problems with other degrees, I guess I should restrict
to characteristic zero, after all.

I was hoping for truly full generality, but I'll settle for full
generality in characteristic 0.

quasi

Setting aside the nonzero characteristic cases, the search
for roots in a field leads naturally to a discussion of
explicit formulas, like the quadratic case, for a polynomial
of degree n. Ultraradicals, ie. solutions to equations like:

x^n + x = A

can be used to provide such formulas. However it is known
already in the n=3 case that the subexpressions of these
formulas can take one outside the ground field, into an
extension field, before potentially returning to a value
for the root in the ground field. That is, one may have
a real cubic with a real root, but the expression for the
cubic in terms of radicals may involve imaginary roots.

There are ways to work around that difficulty in the cubic
case (by using more complicated formulas), but it indicates
the difficulty even with an explicit formula for determining
whether the final value belongs to a given field.

regards, chip
.

Relevant Pages

  • -- reducibility in K[x]
    ... has_root(f) = true if f has a root in K, ... it suffices to consider root testing. ... Thus, for c in K, n in N, define the boolean function is_pow by ... My conjecture is "no". ...
    (sci.math)
  • Re: -- reducibility in K[x]
    ... has_root(f) = true if f has a root in K, ... Thus, for c in K, n in N, define the boolean function is_pow by ... Given an arbitrary field K together with the following effective ... My conjecture is "no". ...
    (sci.math)
  • Re: -- reducibility in K[x]
    ... has_root(f) = true if f has a root in K, ... Consider the polynomials of the form x^n - c, where c is in K. Testing ... Thus, for c in K, n in N, define the boolean function is_pow by ... My conjecture is "no". ...
    (sci.math)
  • Re: -- reducibility in K[x]
    ... has_root(f) = true if f has a root in K, ... Consider the polynomials of the form x^n - c, where c is in K. Testing ... Thus, for c in K, n in N, define the boolean function is_pow by ... My conjecture is "no". ...
    (sci.math)
  • Re: -- reducibility in K[x]
    ... has_root(f) = true if f has a root in K, ... it suffices to consider root testing. ... Thus, for c in K, n in N, define the boolean function is_pow by ... My conjecture is "no". ...
    (sci.math)