- Aug 6 9:49 PM--- In primenumbers@yahoogroups.com, Peter Kosinar <goober@...> wrote:

> My take on the more rigorous phrasing goes like this:

Nicely put. I'm scratching my head trying to figure out how or where I got the notion that the prime factors of the form +/- 1 (mod 10) were raised to odd powers. That restriction is clearly not true, as you have observed.

> The set A = { F(x,y) | gcd(x,y) = 1 } contains integer T

> if and only if:

> - All (prime) factors of T are of the form +/- 1 (mod 10), OR

> - T is divisible by 5 and all (prime) factors of (T/5) are of

> the form +/-1 (mod 10).

Mark

>

> >> If x and y are relatively prime, the conjecture would be modified to

> >> this: If A is the set of all numbers of the form 5x^2 + 5xy + y^2, with

> >> x and y relatively prime, then A contains *only* and *all* of those

> >> numbers which are +/- 1 mod 10 primes raised to an odd power, the prime

> >> 5 to the first power, and the composites that can be made from their

> >> products.

> >

> > Perhaps. I thought my statement more succinct though.

>

> More succint? Yes. As strong? No. Mark's conjecture characterizes

> (a slightly different) set A fully (i.e. he describes what *is* and

> what *is not* in it), while yours provides a condition which sufficient,

> but not necessary for an integer to be member of A.

>

> >>> I bet it could be proven.

>

> Depending on how understands Mike's statement, it might be

> provable, or it might be false :-)

>

> Mike says that:

> (1) A contains +/- 1 (mod 10) primes raised to odd powers.

> (2) Prime 5 raised to first power.

> (3) Composites made from products of (1) and (2).

> (4) Nothing other than required by (1), (2) and (3).

>

> The (potential) problem lies in interpretation of (3).

>

> In order to simplify the notation, let F(x,y) = 5x^2 + 5xy + y^2.

> Since F(3,4) = 11^2, 11^2 belongs to Mike's set. Since it's not

> covered by conditions (1) and (2), it must have been introduced by

> condition (3) (applied to numbers 11 and 11, which belong to the

> set by (1)). The problem is that condition (3) cannot be applied

> the same way to 5 and 5 (as introduced by condition (2)); the number

> 25 can not be expressed as F(x,y) with relatively prime x and y.

>

> My take on the more rigorous phrasing goes like this:

> The set A = { F(x,y) | gcd(x,y) = 1 } contains integer T

> if and only if:

> - All (prime) factors of T are of the form +/- 1 (mod 10), OR

> - T is divisible by 5 and all (prime) factors of (T/5) are of

> the form +/-1 (mod 10).

>

> If we omit the gcd(x,y) = 1 condition, the set B = { F(x,y) }

> will be the same as set A, plus multiplication by any square.

>

> > Perhaps again, but I think its status will remain

> > 'empirical observation' for quite some time. Since

> > the qfbsolve procedure presupposes that it is true,

> > and the good doctor declined to comment upon it.....

>

> There is no "presupposing" about qfbsolve(). The good doctor

> David did provide a hint that qfbsolve() works for ALL primes

> P of the form described above and also provided a pointer to

> the relevant book. Considering that Pari/GP is open-source,

> you could also look at the guts of qfbsolve(), see how (easy)

> and why (difficult) it works with your own eyes :-)

>

> If I recall correctly, it uses a modified Cornacchia

> algorithm (http://en.wikipedia.org/wiki/Cornacchia%27s_algorithm)

> to either find a representation of any prime P or to declare

> that prime P cannot be represented by that quadratic form.

>

> The good doctor also provided a handy trick to deal with products:

> If S = F(a,b) and T = F(c,d), then ST = F(ad - bc, 5ac + 5bc + bd).

> This, together with the trivial observations F(1,0) = 5 and

> F(0,y) = y^2 shows that the set B contains all the numbers

> described above (i.e. the "if" part of the equivalence).

>

> It takes a bit more effort to do the same for set A; mainly

> because the "product" rule doesn't preserve the "relatively

> prime" property, but unless I overlooked something, this part

> should be doable too, without too much effort.

>

> Finally, let's dispel some of the misconceptions related to qfbsolve:

>

> > qfbsolve(Q,p)

> >

> > [snip]

> >

> > The algorithm used runs in probabilistic polynomial

> > time in p (through the computation of a square root of D

> > modulo p); it is polynomial time in D if Q is imaginary,

> > but exponential time if Q is real (through the computation

> > of a full cycle of reduced forms). In the latter case,

> > note that bnfisprincipal provides a solution in heuristic

> > subexponential time in D assuming the GRH.

> > --

> >

> > As to the status of proofs of conjectures relating

> > to qfbsolve, my guess is that many of them are still

> > empirical.

>

> Nope. The qfbsolve algorithm works and there is a proof

> that it works for all primes and all quadratic forms (giving

> you either the representation or a telling you with

> certainty that one doesn't exist). What we do not know is how

> *long* it takes to find the solution. In case of "nice" forms

> (negative discriminant) we know it runs in polynomial time.

> In case of "ugly" forms (positive discriminant, such as

> the currently discussed form), it can take longer. The runtime

> is still finite, though -- in fact, it's bounded by

> an exponential function.

>

> So no, there is no "still empirical" here -- the existence

> has been proved constructively (via a resonably fast algorithm).

>

> Peter

> - << Previous post in topic Next post in topic >>