Loading ...
Sorry, an error occurred while loading the content.

24368Re: Impossible to Prove ??

Expand Messages
  • Mark
    Aug 6 9:49 PM
    • 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