Wikipedia:Reference desk/Archives/Mathematics/2013 March 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 19

Why is the Integer zero-dimensional?

According to High-dimensional space, the Integers are zero-dimensional, Reals are one-dimensional, and Complex numbers are two-dimensional. Why are the integers zero-dimensional? They expand indefinitely in either direction along an imaginary 'line' (a 1D constuct) so I would have thought they were 1D themselves, much like the reals. --Iae (talk) 14:18, 19 March 2013 (UTC)

Maybe Zero-dimensional space would be helpful here... --CiaPan (talk) 16:29, 19 March 2013 (UTC)

Not really, for me. What part of that would relate to the integers? --Iae (talk) 18:30, 19 March 2013 (UTC)

Topologically, the integers are discrete — there is no way to approach an integer as a limit of other integers. Each integer just sits there all alone by itself. All discrete spaces are zero-dimensional, no matter how many points they have. --Trovatore (talk) 18:32, 19 March 2013 (UTC)

In integers, every integer number n (ie. every point of the space) creates a singleton {n}, which is a clopen set. Those singletons form a topological base for integers, and Zero-dimensional space says that a space with such base is zero-dimensional (with respect to the small inductive dimension). --CiaPan (talk) 06:37, 20 March 2013 (UTC)

Thanks. This runs counter to my intuition of dimensions, but I know little about topological spaces. Thanks for the links. --Iae (talk) 10:38, 20 March 2013 (UTC)

Fibonacci n

In Binet's formula

$F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}$

is it possible to isolate n? Pokajanje|Talk 15:45, 19 March 2013 (UTC)

I haven't worked it out in detail, but since $\psi =-{\frac {1}{\varphi }}$, you can mulitply through by $\varphi ^{n}$ and get a quadratic equation in $\varphi ^{n}$. Use the quadratic formula on that, being careful which root you use, and take logs. AndrewWTaylor (talk) 15:59, 19 March 2013 (UTC)

I can reduce things to $F_{n}{\sqrt {5}}=\varphi ^{n}+{\frac {1}{\varphi ^{n}}}$, but it seems like there's one variable too many. (And, sorry, the quadratic equation you describe isn't obvious to me.) Pokajanje|Talk 20:24, 19 March 2013 (UTC)

Multiply both sides of the following equation $F_{n}{\sqrt {5}}=\varphi ^{n}+{\frac {1}{\varphi ^{n}}}$ through $\varphi ^{n}$, and subtract the first side from both sides, then replace $\varphi ^{n}$ with t or x. You'll get a quadratic equation in t or x, whose roots are then computed through the consecrated formula. Extract then the logarithm base $\varphi$ from it/them in order to obtain n. — 79.113.221.97 (talk) 21:10, 19 March 2013 (UTC)

That would mean that $\varphi ^{n}={\frac {F_{n}{\sqrt {5}}-{\sqrt {{5F_{n}}^{2}-4}}}{2}}$. Therefore, $n=\log _{\varphi }({\frac {F_{n}{\sqrt {5}}-{\sqrt {{5F_{n}}^{2}-4}}}{2}})$ (I use that root because $F_{n}{\sqrt {5}}>{\sqrt {{5F_{n}}^{2}-4}}$ and $\varphi ^{n}$ cannot be negative.) Can that be reduced further? Pokajanje|Talk 22:14, 19 March 2013 (UTC)

Uhm... I thought this was about finding n when F_n is known... was I wrong ? :-\ — 79.113.221.97 (talk) 23:49, 19 March 2013 (UTC)

That's what I thought too. For all n, Fn is the closest integer to :${\frac {\varphi ^{n}}{\sqrt {5}}}\,.$

So, given a Fibonnacci number, multiply it by the square root of 5, then take log base phi, and round to the nearest integer, right? Bubba73 ^{You talkin' to me?} 03:09, 20 March 2013 (UTC)

I thought that formula I just found was the way to derive n from F_n. Pokajanje|Talk 03:45, 20 March 2013 (UTC)

To find $\varphi ^{n}$ you want to take the larger of the two roots of the quadratic (if n is odd both roots are positive, but the smaller root is $\varphi ^{-n}$). So

$\varphi ^{n}={\frac {F_{n}{\sqrt {5}}+{\sqrt {{5F_{n}}^{2}+(-1)^{n}4}}}{2}}\approx F_{n}{\sqrt {5}}$

$\Rightarrow n\approx \log _{\varphi }(F_{n}{\sqrt {5}})$

which is what Bubba73 said. Gandalf61 (talk) 14:32, 20 March 2013 (UTC)

I'm not sure it's appropriate to round it off in this case. Also, how did you get $+4(-1)^{n}$? The quadratic I get is $0=(\varphi ^{n})^{2}-\varphi ^{n}F_{n}{\sqrt {5}}+1$. Pokajanje|Talk 16:36, 20 March 2013 (UTC)

Your quadratic is not quite correct because $\psi =-{\frac {1}{\varphi }}$ so you have to take care with signs (or split into even and odd cases). Try a couple of numerical examples:

$\varphi ^{2}={\frac {2{\sqrt {5}}+6}{4}}={\frac {F_{2}{\sqrt {5}}+{\sqrt {{5F_{2}}^{2}+4}}}{2}}$

$\varphi ^{3}={\frac {8{\sqrt {5}}+16}{8}}={\frac {F_{3}{\sqrt {5}}+{\sqrt {{5F_{3}}^{2}-4}}}{2}}$

Gandalf61 (talk) 16:56, 20 March 2013 (UTC)

Rounding off as I described is appropriate because the procedure gets close to the proper integer very quickly. Bubba73 ^{You talkin' to me?} 18:21, 20 March 2013 (UTC)

Speed isn't that much of a factor here, because a computer's going to be doing all the calculations. Pokajanje|Talk 04:12, 21 March 2013 (UTC)

The method I gave is very fast. If you have calculated the square root of 5 and phi in advance, it takes one multiplication, one log, and one round. Bubba73 ^{You talkin' to me?} 04:15, 21 March 2013 (UTC)

Postscript: if you work it out, the difference between -4 and +4(-1^x) actually isn't that different. Plot the graphs of the functions and you'll see they're mostly identical. Pokajanje|Talk 03:21, 21 April 2013 (UTC)

Period of a repeating sequence

Hi,

I was wondering if anyone could help me prove something. Basically I’ve got a problem where I have a bunch of variables that vary periodically over time, forming a ‘sequence’, and I want to know when that sequence repeats. If the functions describing the variables are $f_{1}(t)\ldots f_{N}(t)$, then they can be put in a vector:

${\vec {x}}(t)={\begin{bmatrix}f_{1}(t)\\\cdots \\f_{N}(t)\end{bmatrix}}$

So now the idea is to find what the smallest value of ${\Delta }t$ such that ${\vec {x}}(t+{\Delta }t)={\vec {x}}(t)$.

One case I'm interested in is when the functions don't repeat within their periods (for example, they're saw-tooth waves). In this case working out when ${\vec {x}}(t)$ repeats is easy. For all the functions we can say:

$f_{n}(t+{\Delta }t)=f_{n}(t)\Leftrightarrow {\Delta }t=kT_{n},k\in \mathbb {Z}$

Where $T_{n}$ is the period of the nth function. Then for ${\vec {x}}(t)={\vec {x}}(t+{\Delta }t)$:

${\Delta }t=k_{1}T_{1}=\ldots k_{N}T_{N},k_{1},\ldots k_{N}\in \mathbb {Z}$

From which we can immediately conclude (by the definition of the greatest common divisor) that the smallest ${\Delta }t$ is:

${\Delta }t=\gcd(T_{1},\ldots T_{N})$

However, the other case I'm interested in is when the functions repeat once within their period, specifically when they are triangle waves. Intuitively I would believe that in this case (triangle waves) the sequence repeats when:

${\Delta }t={\gcd(T_{1},\ldots T_{N}) \over 2}$

But I can't figure out how to prove this. Can anybody think of a way?

203.167.139.208 (talk) 20:40, 19 March 2013 (UTC)

Your functional notation suggests that t is continuous, but your use of GCD suggests that it is discrete. If it's discrete, I'm not sure that there is a unique standard definition for a triangle wave. However, supposing that $f_{2}(t):=t\%2$ is one such (with the programmer's definition of % as the modulo operation) and $f_{4}(t):=\min(t\%4,4-t\%4)$ is another, then we have a counterexample because your $\Delta t={\frac {\gcd(2,4)}{2}}=1$ and obviously not all values are the same. (I unfortunately don't immediately have any idea for what it is in that case, so I'll first see if my interpretation is even correct.) --Tardis (talk) 05:53, 20 March 2013 (UTC)

Sorry, what I meant was least common multiple, not gcd, whoops! But I don't understand how either imply that t is discrete? It does imply that the periods T1...TN are integers, but even then, if the meaning of LCM() is extended I think it will still work with non-integers (i.e. if LCM(a,b) is taken to mean 'the smallest number that is an integer multiple of both a and b'). But yes, if t were discrete I wouldn't have expected my above intuition to be right because it's based on the fact that a (continuous) triangle wave is symmetrical. 118.93.174.101 (talk) 09:21, 20 March 2013 (UTC)

The implication arises because (with your definition, which is the only sensible one I know) neither $\gcd(1,\pi )$ nor ${\text{lcm}}(1,\pi )$ exist. Of course, you can restrict to rational periods (technically: commensurate periods), but you didn't say so, and that's relatively uncommon. Assuming that ${\vec {x}}(t+{\Delta }t)={\vec {x}}(t)$ is meant to apply at every t, your statement about triangle waves is still false, as the period cannot be smaller than the period of any component, and half the lcm can be (consider two periods, one a multiple of the other). You might also mean $\min\{\Delta t\in \mathbb {R} ^{+}:\exists t\;\forall k\in \mathbb {Z} \;\;{\vec {x}}(t+k\Delta t)={\vec {x}}(t)\}$, in which case I think it's rather more complicated with all the recrossings. --Tardis (talk) 13:04, 20 March 2013 (UTC)

Ok, fair enough, I think made too many unspoken assumptions in the question, and you comments has been helpful in pointing out the pitfalls in my argument above - but let me rephrase the question. If I have a set of triangle waves, each with an integer period, what is the 'period' of the whole set? By 'period' I mean what you said above ($\min\{\Delta t\in \mathbb {R} ^{+}:\exists t\;\forall k\in \mathbb {Z} \;\;{\vec {x}}(t+k\Delta t)={\vec {x}}(t)\}$). I do see what you mean by it being complicated by the recrossings - since there are points where x(t) takes on the same value it has before, but the sequence as a whole isn't 'repeating'; but that's why I'm asking for help :). 203.167.139.208 (talk) 19:56, 20 March 2013 (UTC)

(One more assumption: $T_{i}$ should be even, so define $H_{i}:=T_{i}/2$.) Well, now that we have a precise problem, what do we know? Each $f_{i}(t):=g_{i}((t+a_{i})\%T_{i})$ with $a_{i}\in [0,H_{i}),g_{i}(x):=\min\{x,T_{i}-x\}$ (the precise values of course do not matter, and only half the phases need be considered). To have $g_{i}(x)=g_{i}(y)$ we need $x=y$ or $x+y=T_{i}$. To have $f_{i}(t)=f_{i}(t+\Delta t)$ we then need $(t+a_{i})\%T_{i}=(t+\Delta t+a_{i})\%T_{i}$ (that is, $\Delta t=k_{i}T_{i}$) or $(t+a_{i})\%T_{i}+(t+\Delta t+a_{i})\%T_{i}=T_{i}$ (that is, $\Delta t=k_{i}T_{i}-2(t+a_{i})$). We can't neglect the simpler case by setting $t=-a_{i}$ in the complicated one because t must be shared for all i. In either case, $\Delta t$ must be even, so define $h:=\Delta t/2$.

Then we apply the Chinese remainder theorem: for any given t, we have a number of congruences of the form $h\equiv 0{\pmod {H_{i}}}$ or $h\equiv -t-a_{i}{\pmod {H_{i}}}$. If we take the latter case for all i, a solution exists iff $\forall i,j\;a_{i}\equiv a_{j}{\pmod {\gcd(H_{i},H_{j})}}$. We can choose the former case for any i by defining $a'_{i}=-t\%H_{i}$ (that is, we may conservatively shift it so that its minima are under consideration); any non-coprime pairs of (half-) periods will define a set of allowed restrictions (that is, sets of i for which we use $a'_{i}$) and values of t. In particular, if $H_{i}=H_{j}$ but $a_{i}\neq a_{j}$ we must substitute at least one one of them; the other must then have the value it would have were it substituted, so we may as well say that we must substitute both. (Then the two are equivalent and we can drop one of them.)

Beyond this, I don't see a particular approach beyond considering each $(H_{i},H_{j})$, finding the required substitutions (substituting both will always work, of course, and devolves to the sawtooth case) and constraints on t (which will eventually be subject to its own Chinese remainder problem from all the half-substituted pairs) via constraint propagation, and then finding h for each allowed system. As for actually finding the answer, it might be simpler to do it inductively by keeping a set of allowed $(t,h)$ pairs and extending/filtering it as you consider each function (extending to reach the new LCM trivial answer). --Tardis (talk) 03:02, 23 March 2013 (UTC)

See Almost periodic function. Bo Jacoby (talk) 14:27, 20 March 2013 (UTC).