Dream Equation
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 3
 Joined: Wed Dec 31, 2008 5:53 am UTC
Dream Equation
So I've been having this dream over and over again. The dream itself doesn't matter except in that it's long and strange and very nightmarish. But a common thread in this dream is that it is very important that I "solve" the following problem: T((T(t+1)+1)=T(t). I've never seen it before in my life, and I'm honestly a bit afraid to think about it too hard when I'm awake lest it make me dream about it more. From my efforts in my dream, I'm pretty sure it is a recursively defined sequence of some sort, where T is a map from N into N, but I can't be sure of it. One obvious sequence that works is any constant sequence, but aside from that I can't really make heads or tails of it. If anyone recognizes it or can shed some light onto it, I'd be very grateful. I've been having this dream multiple times a night and wake up from it very upset each time. It might help that the dream itself has oddly recursive elements to it. Thanks.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Dream Equation
There is the trivial solution, T(x)=a constant, for all x.
Re: Dream Equation
There's a really easy way to solve this. Take the inverse of T on both sides and you end up with:
[math]T(t+1) + 1 = t[/math]
[math]T(t+1) = t  1[/math]
The solution is: [imath]T(t) = t  2[/imath]
You can quickly verify that this is a solution to T(T(t + 1) + 1) = T(t)
At least, that's one possible solution.
[math]T(t+1) + 1 = t[/math]
[math]T(t+1) = t  1[/math]
The solution is: [imath]T(t) = t  2[/imath]
You can quickly verify that this is a solution to T(T(t + 1) + 1) = T(t)
At least, that's one possible solution.
Last edited by Sagekilla on Sun Nov 21, 2010 1:22 am UTC, edited 1 time in total.
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.
Re: Dream Equation
Ah, but that's assuming its invertible. If its not invertible then it would be harder to solve.
Re: Dream Equation
Kurushimi wrote:Ah, but that's assuming its invertible. If its not invertible then it would be harder to solve.
Yes, it is a bit of a big assumption. That's merely one solution, among potentially many. I don't know what the standard techniques
are for solving these sorts of recurrence relations, since this is can be nonlinear in a way.
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Dream Equation
I've found a couple of other solutions. Let f(x) be the fractional part of x, i.e. f(x)=xfloor(x). Then 2f(x/2), f, f(2x)/2, f(3x)/3, f(4x)/4, f(5x)/5, etc. are all solutions to this equation.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 Eebster the Great
 Posts: 3484
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Dream Equation
If the map is onetoone that would seriously limit the number of solutions. But without any such restrictions you will find there are a whole lot of them.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Dream Equation
Eebster the Great wrote:If the map is onetoone that would seriously limit the number of solutions. But without any such restrictions you will find there are a whole lot of them.
In fact, there is a unique onetoone function T: R > R which satisfies the equation, as was pointed out by sagekilla.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 Eebster the Great
 Posts: 3484
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Dream Equation
skeptical scientist wrote:Eebster the Great wrote:If the map is onetoone that would seriously limit the number of solutions. But without any such restrictions you will find there are a whole lot of them.
In fact, there is a unique onetoone function T: R > R which satisfies the equation, as was pointed out by sagekilla.
There is a unique invertible transformation, but there may be more onetoone transformations. To be invertible, it must be onetoone and onto.
That said, I do not know of any other onetoone solutions for this equation.
Re: Dream Equation
Eebster the Great wrote:skeptical scientist wrote:Eebster the Great wrote:If the map is onetoone that would seriously limit the number of solutions. But without any such restrictions you will find there are a whole lot of them.
In fact, there is a unique onetoone function T: R > R which satisfies the equation, as was pointed out by sagekilla.
There is a unique invertible transformation, but there may be more onetoone transformations. To be invertible, it must be onetoone and onto.
That said, I do not know of any other onetoone solutions for this equation.
Actually, Sagekilla's proof works under the assumption that T has a leftinverse, which holds if and only if T is injective. (More directly, T(x) = T(y) implies x = y, if T is injective, which was the first step in the proof.)
Always program as if the person who will be maintaining your program is a violent psychopath that knows where you live.
If you're not part of the solution, you're part of the precipitate.
1+1=3 for large values of 1.
If you're not part of the solution, you're part of the precipitate.
1+1=3 for large values of 1.
 Talith
 Proved the Goldbach Conjecture
 Posts: 848
 Joined: Sat Nov 29, 2008 1:28 am UTC
 Location: Manchester  UK
Re: Dream Equation
The assumption is T is a bijection, that is, T^{1} exists. That assumption gives that T(t)=t2 and ONLY that solution. If you assume that T isn't a bijection then you can get more solutions, but under that assumption there is only one solution.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Dream Equation
Talith wrote:The assumption is T is a bijection, that is, T^{1} exists. That assumption gives that T(t)=t2 and ONLY that solution. If you assume that T isn't a bijection then you can get more solutions, but under that assumption there is only one solution.
As has now been pointed out multiple times, Sagekilla's proof works under the assumption that T is onetoone; you don't need surjectivity. The only time Sagekilla used the existence of an inverse was in saying that T(T(t+1)+1)=T(t) implies that T(t+1)+1=t, which is also true if you only assume injectivity. So there is a unique injective solution (the function t > t2, which happens to also be surjective). There are also other solutions which fail to be injective, such as any constant function, as well as the family of sawtooth waves in my earlier post.
P.S. how did you get the title "Proved the Goldbach Conjecture"? I'm assuming it wasn't by proving the Goldbach conjecture.
P.P.S. 5000th post! I need to get a life.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 Talith
 Proved the Goldbach Conjecture
 Posts: 848
 Joined: Sat Nov 29, 2008 1:28 am UTC
 Location: Manchester  UK
Re: Dream Equation
I think gmalivuk gave it to me after a parody post I made on a quack thread a few months ago, I quite like it. viewtopic.php?p=2270946#p2270946
P.S grats on 5000, sorry you had to waste it on quoting my pretty unnecessary ramblings.
P.S grats on 5000, sorry you had to waste it on quoting my pretty unnecessary ramblings.
Re: Dream Equation
To be completely honest, I don't think I can contribute much to the mathematics here.
But I would just like to say that a person who has dreams like that is a very awesome person indeed.
But I would just like to say that a person who has dreams like that is a very awesome person indeed.
Re: Dream Equation
Pullarius1 said that T is a map from N to N, so that the only injective solution one may find does not fit the constraints given. Which, exposes some of the nightmarish qualities of this equation: the simples method that may come to one's mind (inverting T) cannot be applied with success.
Let's assume that there is no s!=0 that T(s)=T(0)=T(T(1)+1); from this follows 1<=T(1)+1=0, that's a contradiction.
Now let's assume that there is s!=k that T(s)=T(k). Observe
T(k)=T(T(k+1)+1)=T(T(T(k+1)+2)+1)=T(T(T(T(k+1)+2)+2)+1)=T(T(T(T(T(k+1)+2)+2)+2)+1)=...
and the sequence
k; T(k+1)+1; T(T(k+1)+2)+1; T(T(T(k+1)+2)+2)+1;T(T(T(T(k+1)+2)+2)+2)+1; ...
If two neighboring elements of the sequence above are equal, it implies that from that point, all the elements in the sequence are equal, therefore, the are finitely many s!=k suchT(s)=T(k). However, if two nonneighboring elements are equal, the same thing is implied, which can be shown by induction sililarly like the case with neighboring elements. For examle, if two elements "d" elements apart are equal, every n>[the first element's position with equals some other]th element equals the (n+d)th element. However, if none of the elements are equal, there are infinitely many s!=k suchT(s)=T(k).
Does this lead somewhere? If somehow it could be shown that if two of the elements above are equal, k = T(k+1)+1, it could be shown that for infinitely many s!=0 suchT(s)=T(0). At least that would be a mildly neat property.
Let's assume that there is no s!=0 that T(s)=T(0)=T(T(1)+1); from this follows 1<=T(1)+1=0, that's a contradiction.
Now let's assume that there is s!=k that T(s)=T(k). Observe
T(k)=T(T(k+1)+1)=T(T(T(k+1)+2)+1)=T(T(T(T(k+1)+2)+2)+1)=T(T(T(T(T(k+1)+2)+2)+2)+1)=...
and the sequence
k; T(k+1)+1; T(T(k+1)+2)+1; T(T(T(k+1)+2)+2)+1;T(T(T(T(k+1)+2)+2)+2)+1; ...
If two neighboring elements of the sequence above are equal, it implies that from that point, all the elements in the sequence are equal, therefore, the are finitely many s!=k suchT(s)=T(k). However, if two nonneighboring elements are equal, the same thing is implied, which can be shown by induction sililarly like the case with neighboring elements. For examle, if two elements "d" elements apart are equal, every n>[the first element's position with equals some other]th element equals the (n+d)th element. However, if none of the elements are equal, there are infinitely many s!=k suchT(s)=T(k).
Does this lead somewhere? If somehow it could be shown that if two of the elements above are equal, k = T(k+1)+1, it could be shown that for infinitely many s!=0 suchT(s)=T(0). At least that would be a mildly neat property.
Re: Dream Equation
I've not entirely solved it, but I'm close. (I assume here that T is a function from Z to R.) To make things easier for me, I'm going to use a new function U defined by U(t)=T(t+1). The functional equation now becomes U(U(t))=U(t1).
Obviously U is injective iff T is injective, since U(a)=U(b) is equivalent to T(a1)=T(b1). Blacksails already solved that case, so I'm going to concern myself solely with the case where U is not injective.
(1)If U is not an injection, there exist U(a)=U(b) with a>b. Then U(a1)=U(U(a))=U(U(b))=U(b1). And inductively, U(an)=U(bn) for all positive integers N. Hence, if there is any a and b such that U(a)=U(b), then U is periodic over the interval (∞,a] with period ab.
(2)Let A be the largest possible number such that there exists some B with U(A)=U(B) and B!=A, assuming such a number exists*. Then, for s>A, there is no t such that U(t)=U(s) and s!=t. So U(U(s+1))=U(s) implies U(s+1)=s.
*(3)If there is no such number, then let U(A)=U(B) with A>a and A>B. Then, from part (1), U is periodic over the interval (∞,A] with period AB. But we can repeat this procedure indefinitely, and since A>=a+1, A will eventually tend to infinity. So U is periodic over the entire number line.
The solutions to the equation are the functions U with a "cutoff point" A such that U is periodic over the interval (∞,A), and U(t)=t1 over the interval (A,+∞). A may be at ∞ or +∞, in which case U is the function t1 or U is periodic, respectively. We can now substitute T(t)=U(t1)
TLDR: T has a cutoff point A. For t<A, T(t)=T(tp) for some constant p. For t>A, T(t)=t2. A can be finite, or +∞, or ∞. These conditions are necessary, but not sufficient.
EDIT: Example: T(x)=98 if x<=100, and T(x)=x2 if x>=100. That works.
Obviously U is injective iff T is injective, since U(a)=U(b) is equivalent to T(a1)=T(b1). Blacksails already solved that case, so I'm going to concern myself solely with the case where U is not injective.
(1)If U is not an injection, there exist U(a)=U(b) with a>b. Then U(a1)=U(U(a))=U(U(b))=U(b1). And inductively, U(an)=U(bn) for all positive integers N. Hence, if there is any a and b such that U(a)=U(b), then U is periodic over the interval (∞,a] with period ab.
(2)Let A be the largest possible number such that there exists some B with U(A)=U(B) and B!=A, assuming such a number exists*. Then, for s>A, there is no t such that U(t)=U(s) and s!=t. So U(U(s+1))=U(s) implies U(s+1)=s.
*(3)If there is no such number, then let U(A)=U(B) with A>a and A>B. Then, from part (1), U is periodic over the interval (∞,A] with period AB. But we can repeat this procedure indefinitely, and since A>=a+1, A will eventually tend to infinity. So U is periodic over the entire number line.
The solutions to the equation are the functions U with a "cutoff point" A such that U is periodic over the interval (∞,A), and U(t)=t1 over the interval (A,+∞). A may be at ∞ or +∞, in which case U is the function t1 or U is periodic, respectively. We can now substitute T(t)=U(t1)
TLDR: T has a cutoff point A. For t<A, T(t)=T(tp) for some constant p. For t>A, T(t)=t2. A can be finite, or +∞, or ∞. These conditions are necessary, but not sufficient.
EDIT: Example: T(x)=98 if x<=100, and T(x)=x2 if x>=100. That works.
The preceding comment is an automated response.
Who is online
Users browsing this forum: No registered users and 7 guests