Browse Groups

• ... Let F(x,y) = 5*x^2 + 5*x*y + y^2 Then for any prime p = +/- 1 mod 10 it is straightforward to find integers [x,y] such that F(x,y) = p. In Pari-GP, simply
Message 1 of 18 , Aug 1, 2012
View Source
"Aldrich" <aldrich617@...> wrote:

> 1) If A = 5x^2 + 5xy + y^2, then a subset of A is the complete
> set of all of the +/- 1 mod 10 primes and all of the composites
> that can be made exclusively from them.

Let

F(x,y) = 5*x^2 + 5*x*y + y^2

Then for any prime p = +/- 1 mod 10 it is straightforward to
find integers [x,y] such that F(x,y) = p. In Pari-GP, simply use

xyp5(p)=qfbsolve(Qfb(5,5,1),p);

\\ Example:

print(xyp5(100000000000000000039));

[5355540695, -1733283533]

Now observe that

F(x1,y1)*F(x2,y2) = F(x,y) .... [*]

where

x = x1*y2 - x2*y1
y = 5*(x1 + y1)*x2 + y1*y2

It follows that if N is a positive integer all of whose
prime divisors are congruent to +/- 1 mod 10, then
N may be written in the form F(x,y) where [x,y]
are integers obtainable by repeated use of [*],
after using the procedure "xyp5" for the constituent primes.

> 2) If A = 2x^2 + 2xy + y^2 , then a subset of A is the
> complete set of all of the +1 mod 4 primes and all of
> the composites that can be made exclusively from them.

Let

G(x,y) = 2*x^2 + 2*x*y + y^2

then for any prime p = 1 mod 4, it is straightforward to
find integers [x,y] such that G(x,y) = p. In Pari-GP, simply use

xym4(p)=qfbsolve(Qfb(2,2,1),p);

\\ Example:

print(xym4(100000000000000000129));

[-4418521500, 13389400373]

Now observe that

G(x1,y1)*G(x2,y2) = G(x,y) .... [#]

where

x = x1*y2 - x2*y1
y = 2*(x1 + y1)*x2 + y1*y2

It follows that if N is a positive integer all of whose
prime divisors are congruent to 1 mod 4, then
N may be written in the form G(x,y) where [x,y]
are integers obtainable by repeated use of [#],
after using the procedure "xym4" for the constituent primes.

David
• ... In this example, if p was not known already known to be prime or even if it was a possible value of F(x,y), would the qfbsolve procedure prove it to be so
Message 1 of 18 , Aug 2, 2012
View Source
>
> Let
>
> F(x,y) = 5*x^2 + 5*x*y + y^2
>
> Then for any prime p = +/- 1 mod 10 it is straightforward to
> find integers [x,y] such that F(x,y) = p. In Pari-GP, simply use
>
> xyp5(p)=qfbsolve(Qfb(5,5,1),p);
>
> \\ Example:
>
> print(xyp5(100000000000000000039));
>
> [5355540695, -1733283533]

In this example, if p was not known already known to be prime
or even if it was a possible value of F(x,y), would the
qfbsolve procedure prove it to be so straightaway?
If it had factors that were exclusively +/- 1 mod 10, would
all of the locations of p be immediately evident and its factors automatically identified, or would a search be required? If
it had factors +/- 3 mod 10 would qfbsolve give that information
as well? In laymen's terms, how does the qfbsolve procedure
actually work?

Finally, is there a deductive proof that
F(x,y) = 5*x^2 + 5*x*y + y^2 not only has an infinite number of
+/- 1 mod 10 primes but also all of them, or is that assertion an empirical observation?

Ditto similarly all of the above for G(x,y) = 2*x^2 + 2*x*y + y^2.

Thanks,
Aldrich
• Very neat conjecture Aldrich which I well remember you posted before. I bet it could be proven. Upon a flippant and cursory examination, perhaps your
Message 1 of 18 , Aug 2, 2012
View Source
Very neat conjecture Aldrich which I well remember you posted before. I bet it could be proven.

Upon a flippant and cursory examination, perhaps your conjecture could be expanded:

If A is the set of all numbers of the form 5x^2 + 5xy + y^2, then A contains *only* and *all* of those numbers which are +/- 1 mod 10 primes, +/- 3 mod 10 primes raised to an even power, the prime 2 raised to an even power, the prime 5, and the composites that can be made from their products.

Mark

--- In primenumbers@yahoogroups.com, "Aldrich" <aldrich617@...> wrote:
>
>
> {A,x,y : integers}
>
> 1) If A = 5x^2 + 5xy + y^2, then a subset of A is the complete set
> of all of the +/- 1 mod 10 primes and all of the composites that can be
>
> 2) If A = 2x^2 + 2xy + y^2 , then a subset of A is the complete set
> of all of the +1 mod 4 primes and all of the composites that can be
>
• ... No. ... No. ... It depends crucially on the sign of the discriminant. In the case of G(x,y) = 2*x^2 + 2*x*y + y^2 = (x + y)^2 + x^2 with negative
Message 1 of 18 , Aug 2, 2012
View Source

> if p was not known already known to be prime
> or even if it was a possible value of F(x,y), would the
> qfbsolve procedure prove it to be so straightaway?

No.

> If it had factors that were exclusively +/- 1 mod 10, would
> all of the locations of p be immediately evident and its
> factors automatically identified

No.

> how does the qfbsolve procedure actually work?

It depends crucially on the sign of the discriminant.

In the case of

G(x,y) = 2*x^2 + 2*x*y + y^2 = (x + y)^2 + x^2

with negative discriminant 2^2 - 4*2 = -4,
we may solve G(x,p) = p, for prime p = 1 mod 4,
by finding the Gaussian prime x + y + sqrt(-1)*x
whose norm is p. This is unique, up to multiplication
by powers of sqrt(-1), or conjugation, and may be found
using Algorithm 1.5.3 of CCANT by Henri Cohen.

In the case of

F(x,y) = 5*x^2 + 5*x*y + y^2 = (5*x/2 + y)^2 - 5*(x/2)^2

with positive discriminant 5^2 - 4*5 = 5, there is an infinity
of solutions to F(x,y) = p, for prime p = +/- 1 mod 10.

In this latter case qfbsolve gives a solution
to F(x,y) = p, for prime p = +/- 1 mod 10,
that is unique up to multiplication by unities,
or conjugation. However there is an infinity of unities:
see Hardy and Wright, Section 15.4.

Suppose that we have found [x,y] such that p is the norm of
z = 2*x + y + w*x, where w = (1+sqrt(5))/2 is the fundamental
unit, satisfying w^2 = 1+w, conj(w) = 1-w, norm(w) = -1.
Then we may obtain an infinity of solutions
Z = 2*X + Y + w*X, by multiplying z by any positive integral
power of w^2 = 1+w, or any such power of conj(w^2) = 2-w,
both of whose norms are unity.

For example, you saw that qfbsolve gave

F(x,y) = 5*x^2 + 5*x*y + y^2;
x = 5355540695;
y = -1733283533;
print(F(x,y));

100000000000000000039

from which you may easily obtain

X = 4950185869189924612835721591430071882362137191396995;
Y = -6840988620591034906820556921677926059550551300711158;
print(F(X,Y));

100000000000000000039

by setting Z = z*(1+w)^100.

I recommend
for blow-by-blow solutions of such problems,
using continued fractions.

David
• 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
Message 1 of 18 , Aug 2, 2012
View Source
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.

--- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
>
>
> Very neat conjecture Aldrich which I well remember you posted before. I bet it could be proven.
>
>
> Upon a flippant and cursory examination, perhaps your conjecture could be expanded:
>
> If A is the set of all numbers of the form 5x^2 + 5xy + y^2, then A contains *only* and *all* of those numbers which are +/- 1 mod 10 primes, +/- 3 mod 10 primes raised to an even power, the prime 2 raised to an even power, the prime 5, and the composites that can be made from their products.
>
>
> Mark
>
>
> --- In primenumbers@yahoogroups.com, "Aldrich" <aldrich617@> wrote:
> >
> >
> > {A,x,y : integers}
> >
> > 1) If A = 5x^2 + 5xy + y^2, then a subset of A is the complete set
> > of all of the +/- 1 mod 10 primes and all of the composites that can be
> > made exclusively from them.
> >
> > 2) If A = 2x^2 + 2xy + y^2 , then a subset of A is the complete set
> > of all of the +1 mod 4 primes and all of the composites that can be
> > made exclusively from them.
> >
>
• ... From the archives: qfbsolve(Q,p) Solve the equation Q(x,y) = p over the integers, where Q is a binary quadratic form and p a prime number. Return [x,y] as
Message 1 of 18 , Aug 4, 2012
View Source
>
>
>
>
> > if p was not known already known to be prime
> > or even if it was a possible value of F(x,y), would the
> > qfbsolve procedure prove it to be so straightaway?
>
> No.
>
> > If it had factors that were exclusively +/- 1 mod 10, would
> > all of the locations of p be immediately evident and its
> > factors automatically identified
>
> No.
>
> > how does the qfbsolve procedure actually work?
>
> It depends crucially on the sign of the discriminant.
>
> In the case of
>
> G(x,y) = 2*x^2 + 2*x*y + y^2 = (x + y)^2 + x^2
>
> with negative discriminant 2^2 - 4*2 = -4,
> we may solve G(x,p) = p, for prime p = 1 mod 4,
> by finding the Gaussian prime x + y + sqrt(-1)*x
> whose norm is p. This is unique, up to multiplication
> by powers of sqrt(-1), or conjugation, and may be found
> using Algorithm 1.5.3 of CCANT by Henri Cohen.
>
> In the case of
>
> F(x,y) = 5*x^2 + 5*x*y + y^2 = (5*x/2 + y)^2 - 5*(x/2)^2
>
> with positive discriminant 5^2 - 4*5 = 5, there is an infinity
> of solutions to F(x,y) = p, for prime p = +/- 1 mod 10.
>
> In this latter case qfbsolve gives a solution
> to F(x,y) = p, for prime p = +/- 1 mod 10,
> that is unique up to multiplication by unities,
> or conjugation. However there is an infinity of unities:
> see Hardy and Wright, Section 15.4.
>
> Suppose that we have found [x,y] such that p is the norm of
> z = 2*x + y + w*x, where w = (1+sqrt(5))/2 is the fundamental
> unit, satisfying w^2 = 1+w, conj(w) = 1-w, norm(w) = -1.
> Then we may obtain an infinity of solutions
> Z = 2*X + Y + w*X, by multiplying z by any positive integral
> power of w^2 = 1+w, or any such power of conj(w^2) = 2-w,
> both of whose norms are unity.
>
> For example, you saw that qfbsolve gave
>
> F(x,y) = 5*x^2 + 5*x*y + y^2;
> x = 5355540695;
> y = -1733283533;
> print(F(x,y));
>
> 100000000000000000039
>
> from which you may easily obtain
>
> X = 4950185869189924612835721591430071882362137191396995;
> Y = -6840988620591034906820556921677926059550551300711158;
> print(F(X,Y));
>
> 100000000000000000039
>
> by setting Z = z*(1+w)^100.
>
> I recommend
> for blow-by-blow solutions of such problems,
> using continued fractions.
>
> David
>

From the archives:

qfbsolve(Q,p)

Solve the equation Q(x,y) = p over the integers,
where Q is a binary quadratic form and p a prime number.
Return [x,y] as a two-components vector, or zero if there
is no solution. Note that this function returns only
one solution and not all the solutions. Let D = \disc Q.
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.
The library syntax is GEN qfbsolve(GEN Q, GEN p).
--

As to the status of proofs of conjectures relating
to qfbsolve, my guess is that many of them are still
empirical.

Aldrich
• ... Perhaps. I thought my statement more succinct though. ... Perhaps again, but I think its status will remain empirical observation for quite some time.
Message 1 of 18 , Aug 4, 2012
View Source
--- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
>
> 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.

> >
> >
> > I bet it could be proven.
> >

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

a.
• ... 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),
Message 1 of 18 , Aug 6, 2012
View Source
>> 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
• ... In Philosophy, the term presuppose generally means that the truth of one Proposition depends partly on another that is not explicitly mentioned, so
Message 1 of 18 , Aug 6, 2012
View Source
> > 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 :-)
>

In Philosophy, the term "presuppose" generally means that the
truth of one Proposition depends partly on another that is not
explicitly mentioned, so qfbsolve definitely does necessarily presuppose something about infinities of primes in the structure
of binary quadratic forms in its methods. Lack of deductive
proof for these underlying assumptions introduces a measure of
doubt.

> >
> > 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). >
> So no, there is no "still empirical" here -- the existence
> has been proved constructively (via a resonably fast algorithm).
>

Although I believe in the reliability of Qfbsolve almost as
much I believe in Goldbach's Conjecture, both are actually
empirical observations until deductive proofs can be found.

I think you might be surprised at David's opinion on the
topic unless he has recently recanted. A few years ago he
proof when he constructed a sequence that was all +1 mod 10
factors until about the 10^80 mark, where he had placed a square
of a -1 mod 10 factor. The lack of a counter-example simply
is not proof of truth (old school).

Aldrich
• ... 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
Message 1 of 18 , Aug 6, 2012
View Source
--- 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
>
• ... The main difference is that someone already *has found* a deductive proof of qfbsolve s algorithm correctness (proof of the fact that it always terminates
Message 1 of 18 , Aug 7, 2012
View Source
Let me rephrase:

> Although I believe in the reliability of Qfbsolve almost as
> much I believe in Goldbach's Conjecture, both are actually
> empirical observations until deductive proofs can be found.

The main difference is that someone already *has found*
a deductive proof of qfbsolve's algorithm correctness (proof
of the fact that it always terminates and gives correct result),
which is not (yet) the case with Goldbach's Conjecture. However,
nobody on this list was bored enough to waste time to rewrite
this proof into an e-mail. Instead, the good doctor brought
certain book to your attention and I pointed you at PARI/GP
the algorithm works. Doing one or both might make it easier
to follow the proof of correctness of this algorithm.

In short:
1) qfbsolve() works
2) Someone already proved that unconditionally
(= without relying on unproven conjectures).
3) If you look hard enough, you will be able to find the proof
in literature / online / come up with it yourself.

Peter
• ... In the case in question, it presupposes that Theorem 257 of Hardy and Wright is correct. Like many others, I believe that this is the case. David (per
Message 1 of 18 , Aug 8, 2012
View Source
"Aldrich" <aldrich617@...> wrote:

> qfbsolve definitely does necessarily presuppose
> something about infinities of primes in the structure

In the case in question, it presupposes that
Theorem 257 of Hardy and Wright is correct.

Like many others, I believe that this is the case.

David (per proxy the good book)
• I think that having gone through (at least) 5 editions and been scrutinized by all of the best number theorists in the world for the better part of a century
Message 1 of 18 , Aug 8, 2012
View Source
I think that having gone through (at least) 5 editions and been scrutinized by all of the best number theorists in the world for the better part of a century makes this a safe assumption.
JGM

Subject: [PrimeNumbers] Re: Impossible to Prove ??
Date: Wednesday, August 8, 2012, 1:19 AM

"Aldrich" <aldrich617@...> wrote:

> qfbsolve definitely does necessarily presuppose
> something about infinities of primes in the structure

In the case in question, it presupposes that
Theorem 257 of Hardy and Wright is correct.

Like many others, I believe that this is the case.

David (per proxy the good book)

[Non-text portions of this message have been removed]
• ... My personal copy of the Good Book is edition 5, where Theorem 257 appears on page 222 of the paperback edition. There is a 6th edition
Message 1 of 18 , Aug 11, 2012
View Source
James Merickel <moralforce120@...> wrote:

> having gone through (at least) 5 editions

My personal copy of the Good Book is edition 5, where
Theorem 257 appears on page 222 of the paperback edition.

There is a 6th edition
www.amazon.com/An-Introduction-Theory-Numbers-Hardy/dp/0199219869
with embellishments by Andrew Wiles, Roger Heath-Brown and Joe Silverman.
I do not know how much their Apocrypha adds to the Authorized Version.

David
• ... The presentation was beautifully done, but the calculations looked very difficult. A simpler approach (at least conceptually) should work for those integer
Message 1 of 18 , Aug 11, 2012
View Source
>
> I recommend
> for blow-by-blow solutions of such problems,
> using continued fractions.
>

The presentation was beautifully done, but the
calculations looked very difficult. A simpler
approach (at least conceptually) should work for
those integer binary quadratic forms where the
number of times a particular value appears is
coordinated perfectly with the number of factors
it has.

For my test number I chose x = 44398336 and
y = 258399491 yielding A = 116050602938281481
as a value of A = 25x^2 + y^2, with the goal of
demonstrating its primality or finding factors. Since 'A'
values that have in common modular residues that match
the ones that the test number posses can only reside on
certain rows of y, all of the non-solutions can be eliminated
with a relatively few moduli. In this case, the twenty-nine
prime moduli listed below sieved out all but the two
locations where the test number actually resides. A
valid x = 68132401 is found at y = 35884 yielding factors
from the formula of 4045597 and 28685655773.

A mod 10000 = 1481, A mod 3 = 2, A mod 7 = 1, A mod 11= 8,
A mod 13= 2, A mod 17= 5, A mod 19= 8, A mod 23= 22,
A mod 29= 28, A mod 31= 14, A mod 37= 26, A mod 41= 9,
A mod 43= 6, A mod 47= 39,A mod 53= 9, A mod 59= 2,
A mod 61= 16, A mod 67= 3, A mod 71= 49, A mod 73= 52,
A mod 79= 18, A mod 83= 58, A mod 89= 26, A mod 97= 54,
A mod 101= 27, A mod 103= 73, A mod 107= 59,
A mod 157= 97, A mod 211= 81

Aldrich
• ... Chapter 15 of Hardy/Wright looks to me like the basis for the issquare functions. Can the appropriate issquare for A = 14x^2 + 14xy + y^2 be expressed as
Message 1 of 18 , Aug 11, 2012
View Source
--- In primenumbers@yahoogroups.com, James Merickel <moralforce120@...> wrote:
>
> I think that having gone through (at least) 5 editions and been scrutinized by all of the best number theorists in the world for the better part of a century makes this a safe assumption.
> JGMÂ
>

Chapter 15 of Hardy/Wright looks to me like the basis
for the issquare functions. Can the appropriate issquare
for A = 14x^2 + 14xy + y^2 be expressed as 7(2x + y)^2 = 2A?

To get back to the original conjectures, I don't see how
it immediately follows from Hardy/Wright Theorem 257 that
A = 5x^2 + 5xy + y^2 has as values ALL of the possible
values of primes that are +/- 1 mod 10 while the similar
B = 5x^2 + 25xy + y^2 will not.

I also don't see how it immediately follows that
A = 2x^2 + 2xy + y^2 has as values ALL of the
possible values of primes that are +1 mod 4
while the similar B = 8x^2 + 8xy + y^2 will not.

Surely there must be more to the proofs than just
reading the definitions found in chapter 15.

Aldrich
• ... Let w = (1+sqrt(5))/2 be the fundamental unit. HW prove that every prime p = +/-1 mod 10 is of the form norm(a+b*w) = a^2 + a*b - b^2 for some integer pair
Message 1 of 18 , Aug 11, 2012
View Source
"Aldrich" <aldrich617@...> wrote:

> I don't see how
> it immediately follows from Hardy/Wright Theorem 257 that
> A = 5x^2 + 5xy + y^2 has as values ALL of the possible
> values of primes that are +/- 1 mod 10.

Let w = (1+sqrt(5))/2 be the fundamental unit.
HW prove that every prime p = +/-1 mod 10 is of the form
norm(a+b*w) = a^2 + a*b - b^2
for some integer pair [a,b].

Lemma: Every prime p = +/-1 mod 10 is of the form
norm(2*x+y+x*w) = 5*x^2 + 5*x*y + y^2
for some integer pair [x,y].

Proof: Set x = b, y = a-2*b.

David
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.