Reputation
8,760
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
4 21 60
Impact
~322k people reached

Aug
18
answered Uses of “Collatz induction”?
Aug
17
awarded  Good Question
Aug
17
awarded  Yearling
Aug
17
reviewed Approve Group homomorphisms $\mathbb{Q}\to\mathbb{R}$
Aug
17
comment Uses of “Collatz induction”?
... (and ordinarily we would finish the proof with $P(x) \implies P(2 \cdot x + 1)$) but there doesn't seem to be any way to make it work with the other condition. If we change the statement to the stronger (and dubious) "any set of $x$ numbers can be ordered into a sequence $y_n$ such that if $a \lt b \lt c$ then $y_a, y_b, y_c$ are not in arithmetic progression" then $P(3 \cdot x + 2) \implies P(2 \cdot x + 1)$ is straightforward but $P(x) \implies P(2 \cdot x)$ becomes difficult. I wonder if there is some in-between statement that can work?
Aug
17
comment Uses of “Collatz induction”?
@mlk that version works just as well (since $P(3 \cdot x + 2) \implies P(6 \cdot x + 4)$ by the other condition and $3 \cdot (2 \cdot x + 1) + 1 = 6 \cdot x + 4$). I'm hoping for something where the proof is even simpler than with ordinary induction, even if the result itself is not very interesting. One idea I've been playing with since posting this is "any set of $x$ numbers can be ordered into a sequence $y_n$ such that if $a, b, c$ are in arithmetic progression then $y_a, y_b, y_c$ are not in arithmetic progression.". With this statement we can show $P(x) \implies P(2 \cdot x)$ [cont]
Aug
14
revised Which of the following sets are countable?
a proof is required
Aug
13
comment Uses of “Collatz induction”?
For the other direction, note that if the Collatz conjecture fails we can construct a not-universally-true predicate that still satisfies the induction conditions (just define it to be false on a non-trivial cycle or non-terminating chain and true elsewhere). But that doesn't mean that every statement provable this way implies the CC.
Aug
13
comment Uses of “Collatz induction”?
It is like ordinary induction but instead of starting at $1$ and counting up, start at $1$ and follow the Collatz function backwards. If the Collatz conjecture is true then we can reach every number that way, and if the truth of the predicate at each step is implied by the the previous step then the predicate is universally true. I'm not sure how to make it any more clear.
Aug
13
comment Uses of “Collatz induction”?
I think you are misunderstanding a few different things. If you reverse the implication arrow in the last clause, it is not equivalent. $P(x)$ denotes an arbitrary predicate, not the Collatz function, so it doesn't make sense to say $P^{x}(x)$. And I am not concerned here about bounds on stopping time anyway, I am just looking for an example of of a statement that can be proved this way.
Aug
13
revised Is this assertion about g.c.d. true?
edited tags
Aug
13
answered Is this assertion about g.c.d. true?
Aug
13
comment Is EM-algorithm only for missing data?
en.wikipedia.org/wiki/Expectation%2Dmaximization_algorithm
Aug
13
comment imo question to be explained in a manner so as to a layman
My initial thoughts: if there are $n$ points, for each pivot there are $n$ equivalence classes of angles for the windmill. So we have a directed graph on $n^2$ vertices with one outgoing edge per vertex where each edge corresponds to a change in pivot and angle class. Now we are looking for a cycle which among other conditions must include at least $n$ vertices.
Aug
13
comment imo question to be explained in a manner so as to a layman
Fantastic problem! But the link goes to something unrelated.
Aug
12
accepted Short intervals with all numbers having the same number of prime factors
Aug
12
awarded  Revival
Aug
12
comment An Elementary Algebra (Ratios & Proportions) Problem
Can you define "continued proportion"? Based on the question I guess this means $a_{n+1}-a_n \ge a_n - a_{n-1}$?
Aug
12
revised Please help me this hard circle geometry question
edited tags
Aug
12
reviewed Approve What is the quotient ring $\mathbb{Z}_2[x,y]/(x+y)$?