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

24367Re: [PrimeNumbers] Re: Impossible to Prove ??

Expand Messages
  • Peter Kosinar
    Aug 6, 2012
      >> 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