## 24368Re: Impossible to Prove ??

Expand Messages
• Aug 6, 2012
• 0 Attachment
--- In primenumbers@yahoogroups.com, Peter Kosinar <goober@...> wrote:

> 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).

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.

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
>
• Show all 18 messages in this topic