I do not want to die a brainlet

First I want to make something clear. In this thread I will be discussing a problem but this is not a homework thread. I do not want nor am I asking for a solution. I want guidance. A discussion about how this problem may be approached and if there is someone knowledgeable enough to give references to books or articles that can help me out then that would be great too. I genuinely want to do this myself but I come here because after exhausting all of my knowledge I have come to the conclusion I am missing something fundamental needed to tackle this problem and I don't know where else to look for help. This is the problem:

[math]\text{Prove there is a constant } \epsilon > 0 \text{ with the following property:} \\ \text{If a,b,n are positive integers such that gcd(a+i,b+j) > 1 for every i, j} \in \{1,2,...,n\} \text{ then } \min \{ a,b \} > (\epsilon n)^n [/math]

Partial progress:
I have found and confirmed through various sources that for n=1, the smallest possible [math] \min \{ a, b\} [/math] is 14 and for n=2 it is 104.

They form the pairs (14,20) and (104,6200).
Other pairs I have found for the case n=2 are:
230 5654
494 5300
594 3128
644 5718
650 5704
664 4730
740 4654
740 6992
968 6764
1000 3794
1000 5564
1000 5654
1064 6460
1274 1308
1274 6408
1274 6698
1308 1274
1448 2714

My current understanding of the problem:
The problem is phrased in a way that makes you think [math] \epsilon [/math] have to be very small and that you probably have to advance through contradiction but what I have found with my examples is that [math] \epsilon [/math] does not need to be that small because [math] \min \{a,b \} [/math] grows really fast as you increase n.

For the case n=2 you can see that n^n will simply be 4 while the smallest [math] \min \{a,b \} [/math] is 104, way bigger.

That is why I think this has to be a direct proof that will involve approximating [math] \min \{a,b \} [/math].

Hopefully you can lend me a hand and this thread will be remembered as good.

Other urls found in this thread:

people.uwec.edu/mbirika/invisible_points_claim.pdf
twitter.com/SFWRedditImages

Quick fix. It should be
[math] \text{for every i, j} \in \{ 0,1,2,...,n \} [/math] so the correct full statement is:

[math]\text{Prove there is a constant } \epsilon > 0 \text{ with the following property:} \\ \text{If a,b,n are positive integers such that gcd(a+i,b+j) > 1 for every i, j} \in \{0,1,2,...,n\} \text{ then } \min \{ a,b \} > (\epsilon n)^n [/math]

Bump?

is epsilon a rational or an integer

Any real number with the property works.

I don't know maths. But might it have something to do with coprimes?

so then epsilon equals a really small number?

It has to do with coprimes, but really it is more about the opposite. Numbers that aren't coprime and how often do you get this sort of pattern with two numbers.

I do not rule out that possibility but my conjecture is that it does not have to be.

I think that [math] \epsilon = 1 [/math] would be a valid choice because the way I see it is that the a's and the b's grow really really fast compared to n.

But I could be wrong, maybe epsilon has to be kinda small. That said, I think to tackle this problem you have to forget about the constant part of it and focus more on how quickly the a's and b's grow.

I doubt that this is some unique or important constant. It is just a way of framing the problem.

If two numbers have a gcd of 1 then they are coprime so yes

it is asking to prove:

> you have two sections of the integers in which no pair of numbers is coprime
> The length of one section to the power of itself (times some value) is less than the start of the smaller of the two sections

>> you have two sections of the integers in which no pair of numbers is coprime

Just to clarify note that, for example, a and a+4 could be coprime and that wouldn't rule them out.

You basically only want that each a + i be pairwise coprime with each b + j.

You should specify what your trivial cases are. Obviously if epsilon < 1 and n = 1, this will hold true because min{a,b} will be an integer greater than or equal to one.

I don't get why you even include epsilon in this problem.

Is it already proven for min{a,n} > n^n, min{a,n} > n or something similar?

>I don't get why you even include epsilon in this problem.

This is the way the problem was given to me.

>Is it already proven for min{a,n} > n^n, min{a,n} > n or something similar?

I do not understand this statement and I think that maybe you are misunderstanding the problem.

The way I see it is this:

You should think of n as the variable here. For each n, you can get many many pairs of integers that satisfy the relation.

I gave you many examples of that in the OP. But what I essentially have to prove is that as I increase my n, the values of the corresponding a's and b's have to increase much faster. Faster than n^n in particular.

That just means that if you take a particular n and then you manage to find all the corresponding possible values of a and b, then all those a's and all those b's will be bigger than n^n.

You can also observe that in the examples I gve for the case n=2. All those integers are way waaay bigger than 2^2 and, while it is hard to find examples for n=3 and higher, it makes sense that this pattern would hold.

It is not "common" that you find all these many coprime numbers just sitting next to each other. You must have to go really far up the integers to find valid a's and b's.

>It is not "common" that you find all these many coprime numbers just sitting next to each other. You must have to go really far up the integers to find valid a's and b's.

I meant non-coprme

If it were false then a has to be less than n^n.
So you are proving that 0..n^n is always coprime to b...b+n?

Not at all. You are proving that a, a+1, ...,a+n^n i salways coprime to some b,b+1,...,b + n^n for some big. And that both a and b are actually smaller than n^n

Bump.

Gonna take this opportunity to also simplify the problem because many people are getting confused about epsilon. Another way to see the problem is this:

[math] \text{Prove that if a,b,n are positive integers such that gcd(a+i,b+j) > 1 for every i, j} \in \{0,1,2,...,n\} \text{ then } \min \{ a,b \} \geq n^n [/math]

isn't that a distinct problem, not really simplified?

if the one in OP is true and epsilon >= 1 then it implies this reformulation, but if epsilon < 1 then it's weaker

It is technically a distinct problem but the way I see it, epsilon can definitely be 1. So if I am right about that then this formulation is more straight forward.

from the n=1 case you know e

You only care about positive epsilon so you disregard those negative values.

>e would need to be very small, contrary to what you had said.

I don't understand why that would be. Do you think that for bigger n, epsilon would keep decreasing so drastically? I personally don't think it would. I think it has to go down to at most 1. It shouldn't need to be smaller than that but again, I have no proof to back this up.

>If I were you I'd use even n because at least that puts a bound on e, and just show that the bounds do not approach 0 (if they did then for infinite n the only possible e would be 0).

This is the problem. Suppose that I take an arbitrary n (which is really what needs to be done here). How do I, from that, characterize the related a's and b's? I have no idea. No idea at all. That is why I said I am missing something fundamental needed to approach this problem.

lets take an arbitrary n. Then e would need to be smaller than the nth root of the minimum divided by n. So already you know that as n approaches infinity, epsilon will decrease. But this is only the case if the nth root of the minimum grows slower than n. So basically your goal is to show that the nth root of the minimum grows faster than n. In other words, show that min(a,b)>n^n. This problem isn't too different from the original and I have a feeling this point has already been brought up in this thread.

Yes, indeed. That is my reformulation in The problem is I don't have a way to approach it. I wish I could simply take a limit to infinity but I don't know nearly enough about the a's and b's associated to each n to do this.

If this problem is about coprimes (or non-coprimes, whatever you want to call that) you should look into the zeta function. Solving this might be a lot more complex than just taking a limit.

do you have any example of these for n=4? (103,6199) works for n=3 but i checked up to 10000 for n=4 and found nothing

it would be good to know they exist for more than just the first few n before making such a conjecture

This problem was shown to me in a class on elementary number theory.

If I need Analytic Number Theory for this then I'd be really surprised because none of that has been covered in class.

There exist infinitely many pairs. There is actually an algorithm to generate them. The problem is that the algorithm
1) Is hard to compute
2) Produces a's and b's that are really really reaally far up. Which means that this algorithm does not compute the minimum size of the a's and b's.

Check out this paper. people.uwec.edu/mbirika/invisible_points_claim.pdf

for that pair for n=3, e is bound by ~1.56 This means that to get a lower bound for n=4, one of the two numbers would have to be less than 1526 (I took 1.56^4 and multiplied by 4^4). So even though you checked up to 10,000, there could still be a pair where one number is less than 1526 and one number is greater than 10,000.

uh./? archemedian property.


[eqn]\min\{a,b\} \in \mathbb{R} \implies \exists {N\left(\epsilon , n\right)} \in \mathbb{N} \quad|\quad \frac{1}{N\left(\epsilon , n\right)} < \min\{a,b\}[/eqn]
So [math]\epsilon[/math] is the only unknown and we can solve for it.
[eqn]N\left(\epsilon , n \right) := \left(\epsilon n\right)^n \implies \epsilon = \frac{\sqrt[n]{N}}{n}[/eqn]

[math]\epsilon[/math] is now writen in terms of well defined arguments. and thus existence is proven.

>this post

I'm not OP and don't understand the notation. Could you read out the first line in plain english so that I can understand the logic behind it?

Please explain? Are you assigning each n a different epsilon?

The problem is looking for an epsilon that works for all n's.

you might as well post this on stackexchange, more likely to get a good response than here

yes im saying that for all n, there exists an epsilon.
I suppose you want the existence of an epsilon for all n. my bad.

I think OP's problem is to show that your expression does not approach zero as n approaches infinity. The problem is they don't know what N is in terms of n, so they can't take that limit. What would you go about studying if you want to know N in terms of n?

yes i think the same thing, wondering weither there are numbers n for which ab, dont exist.


the minimum of {a, b} is a real number so there exists a natural number N satisfying 1/N is smaller than the minimum of {a, b}

>yes i think the same thing, wondering weither there are numbers n for which ab, dont exist.
no, see the pdf above

>the minimum of {a, b} is a real number so there exists a natural number N satisfying 1/N is smaller than the minimum of {a, b}
since a and b are integers you can just take N=2, but this doesn't help solve the problem at all

Bump because I am dying inside:

My most recent idea is this: Prove that for each n, the associated a's and b's must have at least n distinct prime divisors.

I think this idea makes sense because we know that "+1" is literally a prime shuffler. if (a,b) > 1 and (a,b+1) > 1 then a must have relatively many primes so that it shares primes with both b and b+1. And then it also has to share primes with b+2, b+3,... b+n.

Similarly a+1 has to share primes b, b+1,...,b+n. And so on.

If we could prove this then we could give a lower bound of [math] \min \{ a,b \} [/math] based on the primorial (the product of the first n primes).

Because notice that
2^2 = 4 < 2*3 = 6
3^3 = 27 < 2*3*5 = 30
But now, this breaks in
4^4 = 256 > 2*3*5*7 = 210

But then as we increase n, it starts working again
13^13 = 302 trillion < primorial(13) = 304 trillion

And then after 13 Primorial(n) grows faster than n^n.

Which means that we could pick epsilon as primorial(9) / (9^9) which roughly equals 0.57 because it is at n=9 that this ratio is at its lowest.

So this would be a valid route for finding an epsilon. Approximating the minimum of a and b based on the primorial of n.

Does anyone who know number theory can find an argument that would support this:

Explicitly:

[math] \text{If a,b,n are positive integers such that gcd(a+i,b+j) > 1 for every i, j} \in \{0,1,...,n\} \text{ then a and b must have at least n distinct prime factors} [/math]

i think 'at least n' might be too high (no hard proof of this though), just since half of a+1,...,a+n and half of b+1,...,b+n are divisible by 2

Well, I think at least n - k, where k is a fixed constant, would also be enough because the primorial will still eventually overpower n^n.

Also note that "at least n" is supposed by my examples. 104 is 2 prime factors. And if you increase n, it makes sense that the minimum amount of prime factors needed will increase.

>And if you increase n, it makes sense that the minimum amount of prime factors needed will increase.
i agree, but i guess my points was that if you increase n by two you 'might' only need 1 more prime factor (could be totally wrong)

stop LARPing you fucking autists

What did he mean by this?

Also, has this problem really not been seen by anyone here before?

this is my first time

is it the Riemann hypothesis or some shit?

It is not the Riemann Hypothesis. I am taking a college level class in elementary number theory. I was given this problem after going over the chinese remainder theorem.

But holy fuck can this be done via the chinese remainder theorem? No fucking way. That is why I feel stumped and want assistance. I mean, maybe there is some way this can be set up to be a system of congruences but then how do you "minimize" the answers of congruences? That is why I ask for help.

bump