On the Erdos Conjecture on arithmetic progression: Part 1
Post by OmnipotentEntity
My roommate and I have been trying off and on to hammer away at the Erdos Conjecture on Arithmetic Progressions for the past year or so. It seems easy enough to prove, but it hasn't been proven yet, it's still an open problem (as an aside, Blake thinks I'm crazy for attacking open problems. Shun the nonbeliever! SHUN! SHUUUUUUUN!) It states that if the sum of the reciprocals of the members of a set "A", which contains only positive integers, diverges, then A contains arbitrarily long arithmetic progressions.
If you followed that you can skip down a ways, I'm going to try to explain it.
A set is simply a group of numbers, it can be infinite (a set of all even numbers,) finite (a set of all numbers less than 100,) or we don't know (a set of all twin primes.) The numbers in the set do not have to follow rules, of course, but most of the useful ones do.
A reciprocal of a number is just 1 divided by that number. The reciprocal of 2 is 1/2. The reciprocal of 45 if 1/45. Easy.
An arithmetic progression is a set of numbers with a common difference. For instance {1,3,5,7} is an arithmetic progression with a length of 4 and a common difference (width) of 2. Whereas {5,12,19} is an arithmetic progression with a length of 3 and a width of 7.
The set {2,3,5,7,11} is not an arithmetic progression, but it contains a few as subsets:
Length 1:
{2}, {3}, {5}, {7}, {11}
Length 2:
{2,3}, {2,5}, {2,7}, {2,11}, {3,5}, {3,7}, {3,11}, {5,7}, {5,11}, {7,11}
Length 3:
{3,5,7}, {3,7,11}
Arbitrarily long/high/etc. This means "pick a number, any number." I can pick one higher than you. What the conjecture is saying is that if you pick any number then it's possible to find an arithmetic progression in that set at least as long as that number.
If you were skipping explanations, stop skipping.
So, the beginnings of a proof, it's not complete yet, which is why I'm posting it here. Any ideas would be appreciated.
The path we're trying for is proof by contrapositive. If P then Q becomes if Not Q then Not P. So our premise becomes "If a set of positive integers "A" contains only arithmetic progression of less than a specified length, then the reciprocal of that set must converge."
To prove this we need to prove that, given a specified maximum length k, the set with the greatest possible sum converges. So... how do we go about this? Induction!
First we need to come up with a way to construct a maximal set. Turns out, this is rather easy to do in practice, but nearly impossible to prove that it's optimal. The method that seems to work is to assume that by locally maximizing the set you globally maximize it.
.... sometimes.
Using the following code I tested out when this approach seems to work, and when it does not.
"1" will always be a member of the maximal set (assume that the maximal series starts with a number larger than one. Subtract 1 from every member of the set, now you have a set with the exact same arithmetic progressions, but it's larger.)
It then tests all of the numbers starting with 2 to see if it can be a member of the set, or if it violates the limitations on arithmetic progression.
Using this method some lengths of arithmetic progression are quite regular:
k = 2: {1,2,4,5,10,11,13,14,28,29,31,32,37,38,40,41,82...}
k = 4: {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,26,27,28,29,31...}
k = 6, k = 10, etc
They generate sequences that are easily defined by an algorithm.
Some are not:
k = 3, k = 5, k = 7, k = 8, k = 9, k = 11.
These generate sequences that rapidly devolve into chaos. Why the difference?
Well, here is algorithm that will generate numbers in the same pattern (it does not check for algorithmic progressions so it's a great deal faster than the last one.)
(This code also gives a more accurate rolling sum estimate using a GMP rational.Great library, I love it.)
So. Why would this algorithm only work on certain k lengths? Think about it, I'll have the answer next blog post. You may consider this your Problem of the Week.
If you followed that you can skip down a ways, I'm going to try to explain it.
A set is simply a group of numbers, it can be infinite (a set of all even numbers,) finite (a set of all numbers less than 100,) or we don't know (a set of all twin primes.) The numbers in the set do not have to follow rules, of course, but most of the useful ones do.
A reciprocal of a number is just 1 divided by that number. The reciprocal of 2 is 1/2. The reciprocal of 45 if 1/45. Easy.
An arithmetic progression is a set of numbers with a common difference. For instance {1,3,5,7} is an arithmetic progression with a length of 4 and a common difference (width) of 2. Whereas {5,12,19} is an arithmetic progression with a length of 3 and a width of 7.
The set {2,3,5,7,11} is not an arithmetic progression, but it contains a few as subsets:
Length 1:
{2}, {3}, {5}, {7}, {11}
Length 2:
{2,3}, {2,5}, {2,7}, {2,11}, {3,5}, {3,7}, {3,11}, {5,7}, {5,11}, {7,11}
Length 3:
{3,5,7}, {3,7,11}
Arbitrarily long/high/etc. This means "pick a number, any number." I can pick one higher than you. What the conjecture is saying is that if you pick any number then it's possible to find an arithmetic progression in that set at least as long as that number.
If you were skipping explanations, stop skipping.
So, the beginnings of a proof, it's not complete yet, which is why I'm posting it here. Any ideas would be appreciated.
The path we're trying for is proof by contrapositive. If P then Q becomes if Not Q then Not P. So our premise becomes "If a set of positive integers "A" contains only arithmetic progression of less than a specified length, then the reciprocal of that set must converge."
To prove this we need to prove that, given a specified maximum length k, the set with the greatest possible sum converges. So... how do we go about this? Induction!
First we need to come up with a way to construct a maximal set. Turns out, this is rather easy to do in practice, but nearly impossible to prove that it's optimal. The method that seems to work is to assume that by locally maximizing the set you globally maximize it.
.... sometimes.
Using the following code I tested out when this approach seems to work, and when it does not.
#include <iostream>
#include <iomanip>
#define MAXITER 1000000
#define MAXK 2
int main() {
int series[MAXITER]; //we can change this later if we need more computingness.
series[0] = 1;
int series_length = 1;
int length_arith_prog = MAXK;
double sum = 1.0;
int n = 2;
std::cout << std::setprecision(20);
for (;series_length<MAXITER;n++) {
int found = 0;
for (int i=0; i < series_length && found == 0; i++) {
int members_arith_prog = 0;
int debug = (n - series[i])%length_arith_prog;
if (!((n - series[i])%length_arith_prog)) { //if between these two numbers it is possible to have an arithmetic progression of the specified length
int common_diff = (n - series[i])/length_arith_prog;
for (int j=1; j < length_arith_prog; j++) {
int mid=((i+1)+(series_length-1))/2; //the +1 and -1 cancel, they're just there to remind me.
int high = series_length;
int low = i+1;
int value = series[i] + j*common_diff;
while (low < high) {
mid = low + ((high - low) / 2); // Note: not (low + high) / 2 !!
if (series[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
if ((low < series_length) && (series[low] == value)) {
members_arith_prog++;
}
}
}
if (members_arith_prog+1 == length_arith_prog) { //found a arithmetic progression!
found = 1;
}
}
if (found == 0) {
series[series_length] = n;
int deriv = series[series_length] - series[series_length-1];
series_length++;
sum += (1.0/n);
std::cout << n << " " << series_length << " " << std::setw(5) << deriv << " " << sum << std::endl;
}
}
}
#include <iomanip>
#define MAXITER 1000000
#define MAXK 2
int main() {
int series[MAXITER]; //we can change this later if we need more computingness.
series[0] = 1;
int series_length = 1;
int length_arith_prog = MAXK;
double sum = 1.0;
int n = 2;
std::cout << std::setprecision(20);
for (;series_length<MAXITER;n++) {
int found = 0;
for (int i=0; i < series_length && found == 0; i++) {
int members_arith_prog = 0;
int debug = (n - series[i])%length_arith_prog;
if (!((n - series[i])%length_arith_prog)) { //if between these two numbers it is possible to have an arithmetic progression of the specified length
int common_diff = (n - series[i])/length_arith_prog;
for (int j=1; j < length_arith_prog; j++) {
int mid=((i+1)+(series_length-1))/2; //the +1 and -1 cancel, they're just there to remind me.
int high = series_length;
int low = i+1;
int value = series[i] + j*common_diff;
while (low < high) {
mid = low + ((high - low) / 2); // Note: not (low + high) / 2 !!
if (series[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
if ((low < series_length) && (series[low] == value)) {
members_arith_prog++;
}
}
}
if (members_arith_prog+1 == length_arith_prog) { //found a arithmetic progression!
found = 1;
}
}
if (found == 0) {
series[series_length] = n;
int deriv = series[series_length] - series[series_length-1];
series_length++;
sum += (1.0/n);
std::cout << n << " " << series_length << " " << std::setw(5) << deriv << " " << sum << std::endl;
}
}
}
"1" will always be a member of the maximal set (assume that the maximal series starts with a number larger than one. Subtract 1 from every member of the set, now you have a set with the exact same arithmetic progressions, but it's larger.)
It then tests all of the numbers starting with 2 to see if it can be a member of the set, or if it violates the limitations on arithmetic progression.
Using this method some lengths of arithmetic progression are quite regular:
k = 2: {1,2,4,5,10,11,13,14,28,29,31,32,37,38,40,41,82...}
k = 4: {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,26,27,28,29,31...}
k = 6, k = 10, etc
They generate sequences that are easily defined by an algorithm.
Some are not:
k = 3, k = 5, k = 7, k = 8, k = 9, k = 11.
These generate sequences that rapidly devolve into chaos. Why the difference?
Well, here is algorithm that will generate numbers in the same pattern (it does not check for algorithmic progressions so it's a great deal faster than the last one.)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <gmpxx.h>
#include <string>
#include <sstream>
#define MAXITER 10000000
for (long int k=2; k<1000; k++) {
mpq_class sum;
sum = 1;
long int series_length = 1;
long int length_arith_prog = k;
long int n = 1;
std::cout << std::setprecision(20);
std::ofstream results;
std::ostringstream ostr;
std::string filename;
ostr << "results-k" << length_arith_prog << "-algo.txt";
results.open(ostr.str().c_str());
results << std::setprecision(20);
for (;series_length<MAXITER;) {
long int powerofn = 0;
long int temp = series_length;
while (temp%length_arith_prog == 0) {
temp /= length_arith_prog;
powerofn++;
}
long int diff = 1;
for (long int i=0; i<powerofn; i++) {
diff += std::pow(2*length_arith_prog-1,i);
}
n += diff;
series_length++;
mpq_class tempsum(1,n);
sum += tempsum;
results << n << " " << series_length << " " << std::setw(5) << diff << " ";
results << sum.get_d() << std::endl;
}
results.close();
std::cout << "Finished k=" << length_arith_prog << std::endl;
}
#include <iomanip>
#include <fstream>
#include <cmath>
#include <gmpxx.h>
#include <string>
#include <sstream>
#define MAXITER 10000000
for (long int k=2; k<1000; k++) {
mpq_class sum;
sum = 1;
long int series_length = 1;
long int length_arith_prog = k;
long int n = 1;
std::cout << std::setprecision(20);
std::ofstream results;
std::ostringstream ostr;
std::string filename;
ostr << "results-k" << length_arith_prog << "-algo.txt";
results.open(ostr.str().c_str());
results << std::setprecision(20);
for (;series_length<MAXITER;) {
long int powerofn = 0;
long int temp = series_length;
while (temp%length_arith_prog == 0) {
temp /= length_arith_prog;
powerofn++;
}
long int diff = 1;
for (long int i=0; i<powerofn; i++) {
diff += std::pow(2*length_arith_prog-1,i);
}
n += diff;
series_length++;
mpq_class tempsum(1,n);
sum += tempsum;
results << n << " " << series_length << " " << std::setw(5) << diff << " ";
results << sum.get_d() << std::endl;
}
results.close();
std::cout << "Finished k=" << length_arith_prog << std::endl;
}
(This code also gives a more accurate rolling sum estimate using a GMP rational.Great library, I love it.)
So. Why would this algorithm only work on certain k lengths? Think about it, I'll have the answer next blog post. You may consider this your Problem of the Week.
You must be logged in to post comments.