20 views

Skip to first unread message

Oct 21, 2003, 3:53:04 PM10/21/03

to

Is there a theorem that states any square can be written as a sum

(including negative terms) of only squares of primes and one so that

no term is repeated twice?

(including negative terms) of only squares of primes and one so that

no term is repeated twice?

16 = 25 - 9

36 = 49 - 9 - 4

64 = 81 - 49 - 25 - 9 + 4 - 1

100 = 81 + 49 - 25 - 4 - 1

144 = 81 + 49 + 9 + 4 + 1

196 = 169 + 49 - 25 + 4 - 1

...

Oct 21, 2003, 4:46:19 PM10/21/03

to

Toni Lassila wrote:

>

> Is there a theorem that states any square can be written as a sum

> (including negative terms) of only squares of primes and one so that

> no term is repeated twice?

>

> 16 = 25 - 9

> 36 = 49 - 9 - 4

> 64 = 81 - 49 - 25 - 9 + 4 - 1

^^>

> Is there a theorem that states any square can be written as a sum

> (including negative terms) of only squares of primes and one so that

> no term is repeated twice?

>

> 16 = 25 - 9

> 36 = 49 - 9 - 4

> 64 = 81 - 49 - 25 - 9 + 4 - 1

square of a prime?

[...]

Hugo

Oct 21, 2003, 5:01:08 PM10/21/03

to

Replace with:

64 = 49 + 25 - 9 - 1

100 = 121 - 25 + 4

Oct 21, 2003, 6:26:31 PM10/21/03

to

In article <433bpvo7387dkpvg0...@no.spam>,

Toni Lassila <to...@nukespam.org> wrote:

>Is there a theorem that states any square can be written as a sum

>(including negative terms) of only squares of primes and one so that

>no term is repeated twice?

Toni Lassila <to...@nukespam.org> wrote:

>Is there a theorem that states any square can be written as a sum

>(including negative terms) of only squares of primes and one so that

>no term is repeated twice?

>16 = 25 - 9

>36 = 49 - 9 - 4

>64 = 81 - 49 - 25 - 9 + 4 - 1

I don't think you need the 1.

64 = 13^2 - 11^2 + 5^2 - 3^2

81 = 11^2 - 7^2 + 3^2

100 = 11^2 - 5^2 + 2^2

144 = 13^2 - 5^2

196 = 17^2 - 11^2 + 7^2 - 5^2 + 2^2

225 = 13^2 + 11^2 - 7^2 - 5^2 + 3^2

256 = 13^2 + 7^2 + 5^2 + 3^2 + 2^2

Actually it seems that all positive integers at least up to 1000 can be

written as differences of sums of squares of distinct primes. I wouldn't

be surprised if this was true for all positive integers, but I don't

immediately see a way to prove it.

Robert Israel isr...@math.ubc.ca

Department of Mathematics http://www.math.ubc.ca/~israel

University of British Columbia

Vancouver, BC, Canada V6T 1Z2

Oct 22, 2003, 8:09:47 AM10/22/03

to

On 21 Oct 2003 22:26:31 GMT, isr...@math.ubc.ca (Robert Israel) wrote:

>In article <433bpvo7387dkpvg0...@no.spam>,

>Toni Lassila <to...@nukespam.org> wrote:

>>Is there a theorem that states any square can be written as a sum

>>(including negative terms) of only squares of primes and one so that

>>no term is repeated twice?

>

>I don't think you need the 1.

>

> 64 = 13^2 - 11^2 + 5^2 - 3^2

> 81 = 11^2 - 7^2 + 3^2

> 100 = 11^2 - 5^2 + 2^2

> 144 = 13^2 - 5^2

> 196 = 17^2 - 11^2 + 7^2 - 5^2 + 2^2

> 225 = 13^2 + 11^2 - 7^2 - 5^2 + 3^2

> 256 = 13^2 + 7^2 + 5^2 + 3^2 + 2^2

>

>Actually it seems that all positive integers at least up to 1000 can be

>written as differences of sums of squares of distinct primes. I wouldn't

>be surprised if this was true for all positive integers, but I don't

>immediately see a way to prove it.

Was this result derived from another result or brute-forced?

Another related question is, is it possible to express the square of

any prime as differences of sums of other squares of distinct primes?

It's certainly possible if one includes 1, but what about without it?

Oct 22, 2003, 8:49:26 AM10/22/03

to

This surely look plausible. A possibly related result due to

Sprague states that any integer larger than 128 can be expressed

as a sum of distinct squares. Using only squares of primes will

make things a little bit more difficult, but there are plenty of

primes around, so one might be able to prove the same result

using squares of primes only, and for a limit larger than 128.

Then you could simply run a computer check for the (finite set of)

excluded values.

Look up e.g. Joe Roberts, "Elementary Number Theory - a Problem

Oriented Approach", ch. XI for ideas leading to Sprague's result.

I don't know, if such a simple approach will work in this case.

Cheers,

Jyrki Lahtonen, Turku, Finland

Oct 22, 2003, 2:26:32 PM10/22/03

to

Robert Israel wrote:

My guess is that the primality is a red herring. What matters is that

the sequence has a growth rate that is not too fast and is moderately

regular.

Martin Cohen

Oct 22, 2003, 2:38:52 PM10/22/03

to

A related question:

I wrote a little program checking how many terms are needed to represent

n by the minimum number of distinct squares of primes.

The program only searched for a maximum of 4 terms. The results for

n<=20:

n Terms Primes in sum

0 4 7 -11 -17 19 (means 0 = 7^2 -11^2 -17^2 +19^2)

1 3 7 11 -13

2 4 5 7 17 -19

3 4 2 -7 -11 13

4 1 2

5 2 3 -2

6 ?

7 ?

8 4 3 -7 -11 13

9 1 3

10 4 3 7 11 -13

11 4 -2 -3 -5 7

12 3 -2 -3 5

13 2 3 2

14 4 -3 -5 -11 13

15 3 -3 -5 7

16 2 5 -3

17 ?

18 ?

19 4 2 -3 -5 7

20 3 2 -3 5

List for n<=200 at

http://www.randomwalk.de/scimath/sumpsq.txt

Can we always find a solution with 5 terms for those n marked with "?".

The list of n where I didn't find a solution with <=4 tems continues:

6,7,17,18,31,41,42,55,60,66,84,89,90,102,103,113,114,127,132,138,162,

180, >200

Hugo Pfoertner

Oct 22, 2003, 3:19:41 PM10/22/03

to

> 6,7,17,18,31,41,42,55,60,66,84,89,90,102,103,113,114,127,132,138,162,

> 180, >200

>

> Hugo Pfoertner

In the meantime Edwin Clark confirmed that 5 terms are suficient. He

writes:

<<

I find that just using the first 12 primes all numbers from 1 to 1123

can be written in the form sum(s[i]*p[i]^2, i=1..k) where s[i] is 1 or

-1,

the primes p[i] are distinct and k <=5

>>

Hugo

Oct 22, 2003, 5:35:46 PM10/22/03

to

Toni Lassila <to...@nukespam.org> wrote:

>

> Is there a theorem that states any square can be written as a sum

> (including negative terms) of only squares of primes and one so that

> no term is repeated twice? [...]>

> Is there a theorem that states any square can be written as a sum

> (including negative terms) of only squares of primes and one so that

In fact every integer > 17163 is representable as a sum of distinct

squares of primes, see 54:7373 below. Also below are reviews of some

papers on this and related topics (by no means complete).

-Bill Dubuque

------------------------------------------------------------------------------

10:283d 10.0X

Sprague, R. Uber Zerlegungen in ungleiche Quadratzahlen.

Math. Z. 51 (1948). 289--290.

------------------------------------------------------------------------------

The author shows in a quite elementary way that every positive integer than

128 is the sum of distinct squares. The proof depends on showing with a small

list of such representations that the integers between 129 and 256 are sums of

distinct squares not exceeding 100. There are exactly 32 integers

2,3,6,7,8,11,...,128 which are not the sum of distinct squares.

Reviewed by D. H. Lehmer

------------------------------------------------------------------------------

10:514h 10.0X

Sprague, R.

Uber Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen.

Math. Z. 51 (1948). 466--468.

------------------------------------------------------------------------------

Let P_n(k) denote the number of partitions of k into distinct parts taken

from 1, 2^n, 3^n, ... . The author proves that there is a positive integer

N_n depending only on n such that P_n(k) > 0 for all k > N_n . In other

words, for each n there are only a finite number of integers which are not

the sums of distinct n th powers. This result for n = 2 has already been

obtained by the author [same vol., 289-290 (1948); these Rev. 10:283].

The method of proof is an application of the Tarry-Escott problem.

Reviewed by D. H. Lehmer

------------------------------------------------------------------------------

11:646a 10.0X

Richert, Hans-Egon

Uber Zerlegungen in paarweise verschiedene Zahlen.

Norsk Mat. Tidsskr. 31, (1949). 120--122.

------------------------------------------------------------------------------

The author generalizes some theorems by Sprague [Math. Z. 51, 289-290, 466-468

(1948); these Rev. 10:283,514] and himself [Math. Z. 52, 342-343 (1949); these

Rev. 11:502] about the partition of numbers into distinct parts. The general

theorem may be stated as follows. Let M be an infinite set of positive

integers m_1, m_2, ... , with the following properties: (A) there exist

integers k >= 2, N >= 0, S > 0, such that each integer x, with N < x <= N+S,

may be partitioned into distinct parts taken from the first k members of M;

(B) S >= m_{k+1}; (C) 2m_i >= m_{i+1} for i>k. Then every integer greater

than N may be partitioned into distinct parts taken from M. The proof is

quite straightforward. As an example, if M is the set of triangular numbers

then (A), (B) and (C) are satisfied with k=8, N=33, S=45. Hence every integer

except 2,5,8,12,23,33 is the sum of distinct triangular numbers.

Reviewed by D. H. Lehmer

------------------------------------------------------------------------------

22:26 10.00

Birch, B. J.

Note on a problem of Erdos.

Proc. Cambridge Philos. Soc. 55 1959 370--373.

------------------------------------------------------------------------------

The following result is proved: given any positive coprime integers p, q,

there exists a number N(p,q) such that every n > N(p,q) is expressible as

a sum of the form n = p^a1 q^b1 + p^a2 q^b2 +..., where the (ai,bi) are

distinct pairs of positive integers. The proof is self-contained and

elementary, but far from trivial.

Reviewed by L. Mirsky

------------------------------------------------------------------------------

24:A103 10.46 (10.48)

Cassels, J. W. S.

On the representation of integers as the sums of distinct summands taken

from a fixed set.

Acta Sci. Math. Szeged 21 1960 111--124.

------------------------------------------------------------------------------

Let A be a sequence of distinct positive integers a_1 < a_2 < a_3 <... ;

A(n) denotes the number of members of A less than or equal to n. For a real

number x, write |x| for the difference between x and the nearest integer. The

main theorem proved is that if (1) lim[A(2n)-A(n)]/log(log n) = oo, and if

(2) sum|a_n t|^2 = oo for every real t in 0<t<1, then every sufficiently

large integer is the sum of distinct elements of A. The author proves his

theorem by an original adaptation of the Hardy-Littlewood circle method.

An outstanding feature of this result is the weakness of the growth condition

(1); this gives the theorem great generality. Earlier work by Roth and Szekeres

[Quart. J. Math. Oxford Ser. (2) 5 (1954), 241-259; MR 16:797] gave estimates

for the number of partitions of a large integer n as the sum of distinct

elements of A, but only at the cost of much stronger conditions corresponding

to (1) and (2).

Erdos and others had conjectured that the conclusion of the theorem would

remain true if condition (2) were replaced by the condition that the sequence

A contains infinitely many numbers in every arithmetic progression. As his

second theorem, the author shows that this is not so: for every e>0 there is

a sequence C such that (i) c_n = O(n^{2+e}), (ii) C contains infinitely

many elements in every arithmetic progression, but (iii) the set of integers

which are sums of distinct elements of C has density less than e. In fact,

a suitable sequence C may be constructed from the Fibonacci numbers.

Reviewed by B. J. Birch

------------------------------------------------------------------------------

26:2387 10.45

Erdos, P.

On the representation of large integers as sums of distinct summands taken

from a fixed set.

Acta Arith. 7 1961/1962 345--354.

------------------------------------------------------------------------------

Let {a_i} be an infinite sequence of positive integers such that every

arithmetic progression contains at least one integer which is the sum of

distinct a's; A(n) is the number of a's not exceeding n . The author

proves by elementary means that if A(n) increases faster than

n^{(sqrt(5)-1)/2}, then every large enough integer is a sum of distinct a's.

This appears much weaker than a result recently obtained by the circle method

by Cassels [Acta Sci. Math. (Szeged) 21 (1960), 111-124; MR 24:A103]; but the

author dispenses with a regularity condition essential to Cassels' argument,

and in fact the theorem as stated becomes false if the exponent 1/2(sqrt(5)-1)

is reduced to 1/2-\eps; it may well be possible to reduce the exponent to

1/2+\eps by improving the method of this paper. The crux is the construction

of a fairly long representable arithmetic progression with not too large

difference; this is achieved by means of Lemma 1, the rest is mopping-up.

Reviewed by B. J. Birch

------------------------------------------------------------------------------

29:63 10.60 (12.30)

Graham, R. L. Complete sequences of polynomial values.

Duke Math. J. 31 1964 275--285.

------------------------------------------------------------------------------

Let S = (s_1,s_2,...) be a sequence of real numbers and P(S) the set of

sums of the form \sum_{k=1}^oo e_k s_k , where e_k is 0 or 1 and all but a

finite number of e_k are 0. If all sufficiently large integers belong to P(S),

then S is said to be complete. It is proved in the paper in a simple and

elementary manner that if f(x) is a polynomial with real coefficients,

f(x) = a0 + a1(x 1) +...+ an(x n), an != 0, (x r) = (x(x-1)...(x-r+1))/r!

then the sequence S(f)=(f(1),f(2),...) is complete if and only if

(1) ak = p_k/q_k for some integers p_k and q_k with (p_k,q_k)=1 and

q_k != 0 for 0 <= k <= n

(2) an > 0

(3) gcd(p_0,p_1,...,p_n) = 1 .

Reviewed by M. J. Wonenburger

------------------------------------------------------------------------------

33:7318 10.45

Folkman, Jon

On the representation of integers as sums of distinct terms from a fixed

sequence.

Canad. J. Math. 18 1966 643--655.

------------------------------------------------------------------------------

Let A be a sequence of positive integers a_1 <= a_2 <= a_3 <=... and

denote by P(A) the set of integers which are the sums of any number of

distinct terms of A , that is, P(A) = {\sum_{n=1}^oo e_n a_n : e_n = 0 or 1,

almost all e_n = 0}. It is proved that P(A) contains all sufficiently large

integers provided that (i) it contains an element of every arithmetic

progression, and (ii) either a_n = O(n^\a) or a_n is strictly increasing

and a_n = O(n^{1+\a}) , where \a is a fixed number in the range 0 <= \a < 1.

The theorems become false for \a > 1. The strictly increasing case confirms a

conjecture of Erdos, who was able only to cope with \a <= (sqrt(5)-1)/2

[Acta Arith. 7 (1961/62), 345-354; MR 26:2387]. The proofs are elementary in

the technical sense.

Reviewed by J. W. S. Cassels

------------------------------------------------------------------------------

48:5994 10A45 (10-04)

Dressler, Robert E.; Parker, Thomas

12,758.

Math. Comp. 28 (1974), 313--314.

------------------------------------------------------------------------------

Authors' introduction: "R. Sprague [Math. Z. 51 (1948), 289-290; MR 10:283]

proved that every positive integer greater than 128 can be expressed as a sum

of distinct perfect squares. He also proved [ibid. 51 (1948), 466-468;

MR 10:514] that, for every integer n >= 2, there exists a largest positive

integer r_n that is not expressible as a sum of distinct n th powers (of

positive integers). In the light of the first reference above, we have

r_2 = 128. Unfortunately, the technique used in the second reference above is

existential and does not give any idea of the size of r_n for n>2. Our

purpose here is twofold: (1) we use a computer to find explicitly the value

of r_3 (it turns out to be 12,758), and (2) in the process we give a new

quantitative proof of Sprague's theorem for n=3."

------------------------------------------------------------------------------

50:9759 10A40

Dressler, Robert E.; Parker, Thomas

An addendum to: "12,758" (Math. Comp. 28 (1974), 313--314).

Math. Comp. 29 (1975), 675.

------------------------------------------------------------------------------

The authors point out that the result proved in the original article had been

announced by R. L. Graham [Duke Math. J. 31 (1964), 275-285; MR 29:63].

------------------------------------------------------------------------------

54:7373 10B35

Dressler, Robert E.; Pigno, Louis; Young, Robert

Sums of squares of primes.

Nordisk Mat. Tidskr. 24 (1976), no. 1, 39--40.

------------------------------------------------------------------------------

It is known [R. Sprague, Math. Z. 51 (1948), 289-290; MR 10, 283] that the

largest integer not representable as a sum of distinct squares is 128. In this

paper, the authors announce that the largest integer not representable as a

sum of distinct squares of primes is 17163. The authors use a lemma due to

H.-E. Richert [Nordisk Mat. Tidskr. 31 (1949), 120-122; MR 11:646] with the

inequality p_{i+1}^2 <= 2 p_i^2 (i >= 5) (p_i denoting the i th prime), and

computational verification for the numbers n in 17163 < n <= 17163 + 503^2.

Reviewed by K. Thanigasalam

------------------------------------------------------------------------------

90h:11011 11B13 (11D85 11P99)

Zannier, U.(I-SLRN)

On a theorem of Birch concerning sums of distinct integers taken from

certain sequences.

Math. Proc. Cambridge Philos. Soc. 106 (1989), no. 2, 199--206.

------------------------------------------------------------------------------

B.J. Birch [same journal 55 (1959), 370-373; MR 22:26] has proved that, for

coprime integers p, q >= 2, every sufficiently large integer may be written

as a sum of distinct terms p^r q^s. J.W. Cassels [Acta Sci. Math. (Szeged)

21 (1960), 111-124; MR 24:#A103] established a more general result by making

use of the circle method of Hardy and Littlewood. Here a different

generalization is presented: Let p >= 2 be an integer and let A be an

infinite set of positive integers such that the quotient of distinct elements

of A is never a power of p. If every arithmetic progression contains a sum of

distinct terms p^r a with r >= 0 and a in A then there is a finite subset

A' of A such that every sufficiently large integer is a sum of distinct terms

p^r a with a in A' . Taking A = {q^s : s >= 0} implies (a more precise form

of) Birch's result since, as is easy to see, every arithmetic progression

contains a sum of distinct powers of p , q and pq . The proof is quite

elementary but by no means trivial. {In (2) the central term must be replaced

by the fractional part of log K/log p+h/m .}

Reviewed by G. Turnwald

------------------------------------------------------------------------------

92j:11115 11P05 (11B13)

Mimura, Yoshio(J-KOBEE)

Partial sums of sequences.

Math. Japon. 36 (1991), no. 4, 677--679.

------------------------------------------------------------------------------

The author gives a generalization of a method used by Sprague to show that all

integers larger than 128 are sums of distinct squares. H.-E. Richert [Norsk

Mat. Tidsskr. 31 (1949), 120-122; MR 11:646], J. L. Brown, Jr. [Amer. Math.

Monthly 83 (1976), no. 8, 631-634; MR 55:2741] and R. L. Graham [Duke Math.

J. 31 (1964), 275-285; MR 29:63] have all dealt with similar questions and the

author's theorem is very close to a generalization given by Brown [op. cit.].

A number of special cases, some of which will be found in the above-mentioned

papers, are worked out. For example [...]

Reviewed by Joe Roberts

------------------------------------------------------------------------------

98a:11016 11B25 (11B05)

Hegyvari, Norbert(H-EOTVO)

Subset sums in N^2 . (English. English summary)

Combin. Probab. Comput. 5 (1996), no. 4, 393--402.

------------------------------------------------------------------------------

A well-known result of J. Folkman [Canad. J. Math. 18 (1966), 643-655;

MR 33:7318] is that given an increasing sequence of positive integers

A = {a_i}_{i=1}^oo <= N whose counting function A(n) = \sum_{a_i <= n} 1

satisfies A(n) > n^{1/2+\d} for all sufficiently large n and a fixed

positive \d, the subset sums set P(A) = {\sum e_i a_i : \e_i in {0,1}}

always contains an infinite arithmetic progression.

In his earlier paper [European J. Combin. 17 (1996), no. 8, 741-749;

MR 97g:11006], the author showed that no similar result holds for sequences on

the plane: there exists a sequence A < N^2 such that the number A(n) of

elements of this sequence in any square |x_i|<n, i=1,2, is A(n) > \a n^2

for all sufficiently large n and a positive constant \a, but P(A) contains

no infinite arithmetic progression.

In the paper under review it is shown, however, that a conclusion of this type

(and in fact, a much stronger conclusion) holds provided that the density

restriction imposed on A is expressed in the "correct" way. The main result

is essentially the following: Theorem. Let A <= N^2 , and let \d be a fixed

positive number. Assume that for any n in N^2 there is an a in A for which

|a-n| <= |n|^{1/8-\d}. Then there exist x_0 in N^2 and linearly independent

d1, d2 in N^2 such that {x0 + x1 d1 + x2 d2 : x1, x2 in N} <= P(A) .

It is also shown that d1 and d2 can always be chosen in such a way that

the angle between these two vectors is "large" and that the exponent 1/8

in the conditions of the theorem cannot be replaced by anything greater than

(sqrt{13}+1)/6 ~= 0.7675.

Reviewed by Vsevolod F. Lev

------------------------------------------------------------------------------

2001c:11014 11B25 (11B75)

Hegyvari, Norbert(H-EOTVO)

On the representation of integers as sums of distinct terms from a fixed set.

Acta Arith. 92 (2000), no. 2, 99--104.

------------------------------------------------------------------------------

An infinite set of distinct positive integers is said to be subcomplete if its

set of subset sums contains an infinite arithmetic progression. P. Erdos asked

for the maximal density of a non-subcomplete set. He proved [Acta Arith. 7

(1961/1962), 345-354; MR 26:2387] that, if the counting function A of a set

is such that A(n) >> n^{(sqrt(5)-1)/2}, then this set is subcomplete. This

result was improved by J. Folkman [Canad. J. Math. 18 (1966), 643-655;

MR 33:7318], who relaxed the condition on the counting function to

A(n) > n^{1/2 + e} for any e>0. No exponent better than 1/2 can be expected

in view of Cassels' construction [J. W. S. Cassels, Acta Sci. Math. Szeged

21 (1960), 111-124; MR 24:A103].

The paper provides a proof that A(n) > 300(n log(n))^{1/2} suffices to ensure

the subcompleteness. The key tool is a result obtained by A. Sarkozy [J. Number

Theory 48 (1994), no. 2, 197-218; MR 95k:11010] and G. A. Freiman [Discrete

Math. 114 (1993), no. 1-3, 205-217; MR 94b:11013] on the structure of the set

of subset sums for sufficiently dense sets (the result is that under such a

kind of hypothesis it contains a long arithmetic progression).

Let us finish this review with two references. Firstly, there is an addendum

to Freiman's quoted paper, namely [Discrete Math. 126 (1994), no. 1-3, 447

MR 1264518]. Secondly, the paper (mentioned in the addendum in the article

under review) by T. Luczak and T. Schoen ["On the maximal density of sum-free

sets", Acta Arith., to appear] contains essentially the same result as the

paper under review.

Reviewed by Alain Plagne

------------------------------------------------------------------------------

2003j:11019 11B75 (11A67)

Chen, Yong-Gao(PRC-NJN)

On subset sums of a fixed set.

Acta Arith. 106 (2003), no. 3, 207--211.

------------------------------------------------------------------------------

Let A be an infinite set of positive integers. The set of subset sums is

defined by P(A) = {\sum_{a in B} a : B <= A; |B|<oo}. The sequence is said

to be subcomplete if P(A) contains an infinite arithmetic progression.

In 1962 Erdos proved that |A(n)| > cn^\a, c>0 , implies the subcompleteness

of A , where \a = sqrt{5}-1/2 and A(n) is the counting function of A .

In 1966 Folkman proved that \a = 1-\eps, and recently the reviewer [Acta Arith.

92 (2000), no. 2, 99-104; MR 2001c:11014] and independently T. Luczak and

T. Schoen [Acta Arith. 95 (2000), no. 3, 225-229; MR 2001k:11018] improved this

result, proving for |A(n)| > c' sqrt{n log n} that the sequence is subcomplete.

In the present paper the author improves our result. He proves that if

|A(n)| > c sqrt{n}, c>0, then A is subcomplete.

The reviewer should mention that Szemeredi has also proved a similar result,

and his proof will appear in the near future.

Reviewed by Norbert Hegyvari

Oct 22, 2003, 5:53:19 PM10/22/03

to

Toni Lassila <to...@nukespam.org> wrote in message news:<ajscpvcb45iqeddbk...@no.spam>...

> On 21 Oct 2003 22:26:31 GMT, isr...@math.ubc.ca (Robert Israel) wrote:

>

> >In article <433bpvo7387dkpvg0...@no.spam>,

> >Toni Lassila <to...@nukespam.org> wrote:

> >>Is there a theorem that states any square can be written as a sum

> >>(including negative terms) of only squares of primes and one so that

> >>no term is repeated twice?

> On 21 Oct 2003 22:26:31 GMT, isr...@math.ubc.ca (Robert Israel) wrote:

>

> >In article <433bpvo7387dkpvg0...@no.spam>,

> >Toni Lassila <to...@nukespam.org> wrote:

> >>Is there a theorem that states any square can be written as a sum

> >>(including negative terms) of only squares of primes and one so that

> >>no term is repeated twice?

> >I don't think you need the 1.

> > 64 = 13^2 - 11^2 + 5^2 - 3^2

> > 81 = 11^2 - 7^2 + 3^2

> > 100 = 11^2 - 5^2 + 2^2

> > 144 = 13^2 - 5^2

> > 196 = 17^2 - 11^2 + 7^2 - 5^2 + 2^2

> > 225 = 13^2 + 11^2 - 7^2 - 5^2 + 3^2

> > 256 = 13^2 + 7^2 + 5^2 + 3^2 + 2^2

> >Actually it seems that all positive integers at least up to 1000 can be

> >written as differences of sums of squares of distinct primes. I wouldn't

> >be surprised if this was true for all positive integers, but I don't

> >immediately see a way to prove it.

> Was this result derived from another result or brute-forced?

Computed, not quite brutally, but now here's a proof (well, almost).

Let p_n be the n'th prime.

Note (by explicit computation) that all integers up to 642 can be expressed

using the first 8 primes, e.g. 642 = 19^2 + 13^2 + 11^2 - 3^2.

The bottleneck, btw, is 2, which can't be expressed using the first 7 primes,

but is 19^2 - 13^2 - 11^2 - 7^2 - 5^2 + 3^2 - 2^2.

Let X_k be the largest positive integer x such that all integers from 1 to x

can be expressed using the first k primes (so X_8 >= 642). Note that

X_8 > p_9^2 = 529. Now if X_k >= p_{k+1}^2, then X_{k+1} >= X_k + p_{k+1}^2

(since for any integer x from X_k + 1 to X_k + p_{k+1}^2, we can subtract

p_{k+1}^2 and obtain an integer that can be expressed using the first k primes).

We will then have X_{k+1} >= p_{k+2}^2 if 2 p_{k+1}^2 >= p_{k+2}^2, i.e.

p_{k+2} <= sqrt(2) p_{k+1}. Now I'm quite sure that this is true

for all k > 3. It certainly is true for k sufficiently large, by the Prime

Number Theorem, but I don't know of explicit estimates. Assuming it is

true, we have X_k >= p_{k+1}^2 for all k >= 8, so X_k -> infinity

as k -> infinity, and any integer can be expressed by taking k sufficiently

large. Moreover, in the expression any negative terms will come from the

first 8 primes.

Oct 22, 2003, 6:08:23 PM10/22/03

to

Robert B. Israel wrote

>

> Computed, not quite brutally, but now here's a proof (well, almost).

>

Clap - clap - clap - bravo!!

Well, they say there are similarities between math and music.

This is pretty true: You can enjoy the performance even if

you do not really understand :-)

(Am I right, when I see a distant connection between your

conjecture (...well, almost...) and Andrica's conjecture?)

With kind regards

Rainer Rosenthal

r.ros...@web.de

Oct 22, 2003, 6:41:30 PM10/22/03

to

This intrigued me so I ran a quick program to test this and found that there

seem to be many possible answers - I found 21 variations for 4^2 = 16 just

using the first 10 primes (2 3 5 7 11 13 17 19 23 29).

seem to be many possible answers - I found 21 variations for 4^2 = 16 just

using the first 10 primes (2 3 5 7 11 13 17 19 23 29).

Eg:

16 = 529 - 361 - 289 + 121 + 25 - 9 (23, 19, 17, 11, 5, 3)

16 = 841 - 361 - 289 - 121 - 49 - 9 + 4 (29, 19, 17, 11, 7, 3, 2)

However there is nothing special about squares, I generated numerous

variations for every integer, positive and negative. I ran the first

2,000,000 results (out of the 3^20 possible) using the first 20 primes and

saw no special pattern - every integer appears to be getting represented

repeatedly by different permutations.

Regards

Manning

Sydney

"Bill Dubuque" <w...@nestle.ai.mit.edu> wrote in message

news:y8zbrs9...@nestle.ai.mit.edu...

Oct 24, 2003, 7:55:57 AM10/24/03

to

On 22 Oct 2003 14:53:19 -0700, isr...@math.ubc.ca (Robert B. Israel)

wrote:

wrote:

>Computed, not quite brutally, but now here's a proof (well, almost).

>

>Let p_n be the n'th prime.

>Note (by explicit computation) that all integers up to 642 can be expressed

>using the first 8 primes, e.g. 642 = 19^2 + 13^2 + 11^2 - 3^2.

>The bottleneck, btw, is 2, which can't be expressed using the first 7 primes,

>but is 19^2 - 13^2 - 11^2 - 7^2 - 5^2 + 3^2 - 2^2.

>Let X_k be the largest positive integer x such that all integers from 1 to x

>can be expressed using the first k primes (so X_8 >= 642). Note that

>X_8 > p_9^2 = 529. Now if X_k >= p_{k+1}^2, then X_{k+1} >= X_k + p_{k+1}^2

>(since for any integer x from X_k + 1 to X_k + p_{k+1}^2, we can subtract

>p_{k+1}^2 and obtain an integer that can be expressed using the first k primes).

>We will then have X_{k+1} >= p_{k+2}^2 if 2 p_{k+1}^2 >= p_{k+2}^2, i.e.

>p_{k+2} <= sqrt(2) p_{k+1}.

Impressive.

>Now I'm quite sure that this is true for all k > 3. It certainly is true for k

>sufficiently large, by the Prime Number Theorem, but I don't know of explicit

>estimates.

So the question is, can we find an example for all integers before the

ratio of subsequent primes p_(k+1)/p_k falls permanently under sqrt(2)

at some k > N? To complete the proof, I think we need a definite upper

bound for N (assumed to be three at the moment).

Oct 24, 2003, 8:13:30 AM10/24/03

to

On Wed, 22 Oct 2003 11:26:32 -0700, Martin Cohen

<martin_...@west.raytheon.com> wrote:

<martin_...@west.raytheon.com> wrote:

>My guess is that the primality is a red herring. What matters is that

>the sequence has a growth rate that is not too fast and is moderately

>regular.

This is actually what I began wondering about when attempting to

formulate the problem. Assuming a set (finite or infinite) of unique

integers, what is the minimal set of integers that covers all possible

integers as a sum of their differences?

It's trivial to prove that there are infinite sequences that are much

denser than the sequence of, say square primes, but that still don't

cover nearly every integer. Take for example the sequence of evens[1],

which fails to cover every odd number etc. So can we construct a

minimally dense sequence that covers all integers and if so, what does

that sequence look like?

This is related to my second conjecture about the sequence of square

primes, which might be reposed as "is it possible to leave out any of

the square primes and still cover all the integers"?

[1] BTW, is this also the densest sequence that fails to do so?

Oct 24, 2003, 6:20:12 PM10/24/03

to

> Hugo Pfoertner wrote:

> >

> > Robert Israel wrote:

> > >

> > > In article <433bpvo7387dkpvg0...@no.spam>,

> > > Toni Lassila <to...@nukespam.org> wrote:

> > > >Is there a theorem that states any square can be written as a sum

> > > >(including negative terms) of only squares of primes and one so that

> > > >no term is repeated twice?

> > >

[...]> >

> > Robert Israel wrote:

> > >

> > > In article <433bpvo7387dkpvg0...@no.spam>,

> > > Toni Lassila <to...@nukespam.org> wrote:

> > > >Is there a theorem that states any square can be written as a sum

> > > >(including negative terms) of only squares of primes and one so that

> > > >no term is repeated twice?

> > >

> > A related question:

> >

> > I wrote a little program checking how many terms are needed to represent

> > n by the minimum number of distinct squares of primes.

> >

6 ?

7 ?

...

[...]

> > Can we always find a solution with 5 terms for those n marked with "?".

>

Edwin Clark wrote:

> <<

> I find that just using the first 12 primes all numbers from 1 to 1123

> can be written in the form sum(s[i]*p[i]^2, i=1..k) where s[i] is 1 or

> -1,

> the primes p[i] are distinct and k <=5

> >>

Although it seems that my question about minimal representations is

considered to be "off topic" in this thread, here is what I've found

so far by brute force search:

http://www.randomwalk.de/sequences/a088910.txt

Hugo Pfoertner

Oct 25, 2003, 8:43:34 AM10/25/03

to

On Wed, 22 Oct 2003 15:09:47 +0300, Toni Lassila <to...@nukespam.org>

wrote:

wrote:

>Another related question is, is it possible to express the square of

>any prime as differences of sums of other squares of distinct primes?

>It's certainly possible if one includes 1, but what about without it?

I've verified that the only prime squares less than (p_8)^2 not

expressible as sums of differences of other prime squares less than

(p_8)^2 are 4 and 9:

25 = 49 - 121 + 169 + 289 - 361

49 = 121 + 289 - 361

121 = 49 - 289 + 361

169 = 25 - 49 + 121 - 289 + 361

289 = 49 - 121 + 361

361 = -49 + 121 + 289

Oct 29, 2003, 5:32:04 PM10/29/03

to

The "minimal" representations, minimizing the largest prime used

in the sum:

:

2^2 = 4 = -29^2 + 19^2 + 17^2 + 11^2 + 7^2 + 5^2

3^2 = 9 = -37^2 + 23^2 + 19^2 + 17^2 + 11^2 + 7^2 + 5^2 + 2^2

5^2 = 25 = -19^2 + 17^2 + 13^2 - 11^2 + 7^2

7^2 = 49 = -19^2 + 17^2 + 11^2

11^2 = 121 = 19^2 - 17^2 + 7^2

13^2 = 169 = 19^2 - 17^2 + 11^2 - 7^2 + 5^2

17^2 = 289 = 19^2 - 11^2 + 7^2

19^2 = 361 = 17^2 + 11^2 - 7^2

23^2 = 529 = 19^2 + 17^2 - 11^2

29^2 = 841 = 19^2 + 17^2 + 11^2 + 7^2 + 5^2 - 2^2

31^2 = 961 = 19^2 + 17^2 + 13^2 + 11^2 + 5^2 - 2^2

37^2 = 1369 = 23^2 + 19^2 + 17^2 + 13^2 + 5^2 - 2^2

41^2 = 1681 = 29^2 + 19^2 + 17^2 + 13^2 + 5^2 - 2^2

= 29^2 + 23^2 + 13^2 + 11^2 + 5^2 - 2^2

43^2 = 1849 = 29^2 + 23^2 + 17^2 + 13^2 + 5^2 - 2^2

47^2 = 2209 = 29^2 + 23^2 + 19^2 + 17^2 + 13^2 + 5^2 - 3^2 + 2^2

= 29^2 + 23^2 + 19^2 + 17^2 + 13^2 + 7^2 - 5^2 - 2^2

53^2 = 2809 = 31^2 + 29^2 + 23^2 + 19^2 + 11^2 - 2^2

If we don't look for the smallest possible maximum prime, but for the

minimum number of terms, there are different representations for

13^2 = 169 = 31^2 - 29^2 + 7^2

= -31^2 + 29^2 + 17^2

29^2 = 841 = 23^2 + 19^2 - 7^2

31^2 = 961 = 29^2 + 13^2 - 7^2

37^2 = 1369 = 31^2 + 23^2 - 11^2

41^2 = 1681 = 31^2 + 29^2 - 11^2

43^2 = 1849 = 37^2 + 23^2 - 7^2

47^2 = 2209 = 37^2 + 31^2 - 11^2

53^2 = 2809 = 47^2 + 31^2 - 19^2

Hugo Pfoertner

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu