/sci/ - Science & Math

im trollop from the other thread

>>2633588
As I already mentioned in the last thread: with an elegant solution you're immediately able to replace 1/3 by an arbitrary real number in [0,1]

trollop here, with an idea.
let's solve a more general idea with 1/3 changed to c, 0<c<1.
first find a sequence of rationals p1/q1, p2/q2,... that converges to c, and that the denominators of the r are strictly increasing.
Put the first p1 integers (out of of q1) into M. then put the next p2-p1 integers (out of q1+q2) into M. then put the next p3-p2 integers (out of q1+q2+q3) into M.
We claim that all arithmetic sequence will intersect M at ratio pi/qi as n gets bigger and this converges to c. this must be proven rigorously, but i have a feeling is correct.

how is it, op?

>>2633632
What does "out of q1" mean?

>>2633632
small correction in this paragraph, to clarify:

Put the first p1 integers (starting from 0) into M. then put the next p2-p1 integers (starting from 1+q1) into M. then put the next p3-p2 integers (starting from 1+q2) into M. etc.

>>2633632
I just thought about this ansatz once. It could work but it'll be quite dirty if it does. I had a non-constructive proof in mind.

>>2633652
To be honest that sounds like a messy approach, and I find it hard to persuade myself that it works even for simple cases c=1/2. Are you sure you can prove this?

>>2633665
i think so, by handwaving.

let 1/2 = pi/qi.

imagine if we take q2 to be much, much greater than q1. then from 1 to q2, "about half" the number are in M and half is not in M, so any AP with small b is expected to cut M in half.

take q3 to be much, much greater than q2, etc.

>>2633654
Intuititvely it is somewhat obvious - you can obviously get to 0, and you can get to 1. What would be nice to do would be to establish some suitable topology or better yet metric on sets of integers so that we could call the density function continuous, which would establish the result immediately. There's some difficulties with this, as you need to explain why you can add 'just enough' to M to be able to increase the density as slightly as you want, though.

Just another hint: you can even prove:
Let 0 < a < 1 be fixed. If (s_i) is a countable family of injective functions
s_i: N -> N
Then there exists a set M which fulfils the following condition:
For each i, the sequence
(s_i({1,2,...,n}) "cut" M) / n
converges to a.
(maybe this hint made it too easy but it's remarkable)

>>2633681
I see your point, but that argument would go through equally well if you didn't take a continuous 'block' of integers every time, and instead spaced your integers out regularly or something. However, then you could easily construct arithmetical sequences for which the conclusion was false. I guess what I'm saying is that arithmetical sequences intersecting a set isn't as random as you seem to be claiming here - you need to do some more work. I agree now that the idea is intuitively sound, though.

I'm assuming "cut" means intersection rather than set subtraction (it makes little difference), and using x rather than 1/3.

Choose any irrational number y. Then let n be a member of M iff ny - floor(ny) < x.

Somebody else can prove it.

I think I thought about this before, but I guess the hint made me realize it had to work:

Obviously this would be fairly easy if we only had a finite number of arithmetical sequences. So enumerate the arithmetical sequences (they are in 1-1 correspondence with pairs (a,b), which are countable), and also define a sequence of rationals q_i monotonically increasing and converging to c. and start with the set A_1={a_1} consisting only of the first arithmetical sequence. Define also M_1={1}. Recursively, construct A_i from A_{i-1} by adding a_i, and extend M_{i-1} to M_i by starting from the last integer we added to M_{i-1} and then selecting the integers we need so that, for the first i terms of sequences in A_i, the density is (as closely as possible) equal to q_i. Now letting i tend to infinity and taking the union of the M_i, we end up with a set M which more or less by construction works.

>>2633743
Good idea! I had another proof in mind which does also work for the "extremely" general case.
But using the equidistribution of {ny} is quite clever.
Does anybody want a proof of >>2633687 or do you still want to think about it?

OP here. If there aren't any objections, I'll show you my solution in ten minutes.

Ok, here's the solution:
Let X_n be identically independently distributed random variable which takes the values 1; 0 with probabilies x; 1-x. The underlying probability space is {0,1}^N (with the probability measure induced by the X_n).
Take v in {0,1}^N randomly. Now look at any function s_i Because of b > 0 the events v_(s_i(n)) = 1 are i.i.d., too. Let M be the set of n such that v_i = 1.
The law of large numbers now implies that the term
1/n * (X_s(1)(v) + X_s(2)(v)+... + X_s(n)(v)) converges to the expected value of X_1 almost surely. The expected value is x.
If there are only countably many sequences s_i the probability that this happens in all sequences is also 1. Therefore we have proved that such a set exists because the probability of constructing it randomly is 1.

>>2633998
A probabilistic argument! That's very nice.

>>2633998
I forgot to say that
1/n * (X_s(1)(v) + X_s(2)(v)+... + X_s(n)(v))
= | s( {1,2,...,n} ) "cut" M | / n

>>2634030
I found it randomly (ha-ha) when I thought about the use of the probabilistic method in additive combinatorics. Most probabilistic proofs can be replaced by a similar counting argument (the first moment method, for example, is only double counting with weights) but this proof doesn't seem to have an obvious "counting analogue".

By the way: it's funny that there are some theorems in Ramsey Theory for which there exist quite exotic proofs. Van der Waerden's theorem and Szemeredi's theorem can be proved by topological dynamics respective ergodic theory. Ramsey's theorem can be proved by the use of Nonstandard models. Hindman's theorem can be deduced from a theorem on topological semigroups. There are many exotic methods in combinatorics. It is quite surprising.