Wikipedia:Reference desk/Archives/Mathematics/2009 December 4

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.

December 4

Same Question As Three Days Ago, But In The Other Direction

Three days ago I started publicly investigating a deterministic sequence of binary numbers created by prepending 1 followed by as few 0s as possible so that each succeeding number is relatively prime to all of its predecessors. I propose that the sequence that is created by appending 1 after as few 0s as possible to get the same outcome is harder to evaluate, and here I do suggest that the sequence is infinite, but am wondering if it might be finite. Looking for its nature, generally. If it is finite, it's probably not much more difficult to see why. On the other hand, proving it infinite may be difficult, if that's the case; and evaluating its growth should make the prospects for its having infinitely many primes effectively nil, as my first instinct. Interested?

There are also various similar and related questions for other bases than base two, of course. I actually started this inquiry in base ten starting with 9, 49, etc., with the rule that relatively prime composite numbers with no zeros are created. It goes pretty far out before terminating with just the smallest of any options for the digit chosen, so a nice question of some difficulty is to find how far out it can possibly go without this limitation. I haven't looked into it.Julzes (talk) 08:15, 4 December 2009 (UTC)

After some consideration and experimentation, I've concluded that this sequence should also be finite, and probably for precisely the same sort of reason. As far as I have taken this sequence, the first three Fermat primes have limited the numbers of 0s in strings to 6 modulo 8. 257 hasn't come up yet, but I expect it to eventually force this to become 6 modulo 16; and then the most likely occurrence to end the sequence will again be 7, 13 and 97 coming up in alternative prospective entries. So, that's pretty much it for the base-2 problem, with only the full number to be evaluated. I have no idea what happens with base 3 or more complicated problems of the kind.Julzes (talk) 19:06, 4 December 2009 (UTC)

I'm not apt to work out the problem here any time soon, so anyone who can program it might consider taking a shot at it. The way I got the solution to the first problem was probably a little lucky in comparison to what I could get into going the other way. 16002 digits is actually rather small compared to what I would guess this problem will take. In base three, the problem could be tractable also, but beyond that I expect that there may not be finitude (though I keep having to correct this assumption). In base three, the non-zero digit is always 2 after beginning 111--in the precisely analogous problem--while higher bases give alternatives. I don't know. The finitude/infinitude of the sequences in higher bases are not patently obvious even with what I already have for base 2. And I now see that there is no clear reason for isolated 0s to end at any point in the base-3 case, so that it may well be infinite.Julzes (talk) 01:58, 5 December 2009 (UTC)

I must amend the last sentence. Any set of odd primes for which the reciprocals of the order of 3 modulo those primes divided by any positive integers summing to 1 is a candidate set for ending the sequence in base three. It would only be a matter of a very long sequence to get an eventual termination, assuming such a set of primes exists.Julzes (talk) 03:29, 5 December 2009 (UTC)

The last is still not quite right, but anyway there is an astronomically large solution involving most likely 5, 7, 13, 17, 19, 37, 41, 193 and 757. Enough said. Nobody is ever going to do any better than approximate the general order of the number!Julzes (talk) 04:07, 5 December 2009 (UTC)

I calculate that there is about a 50% chance that there will be 39.3 billion 2s in place before the sequence would terminate. Given just how long the strings of 0s must commonly be way out there, I stand by my assumption this will never be calculated. Of course, it's theoretically possible.Julzes (talk) 05:25, 5 December 2009 (UTC)

I'm a bit curious, and I'm quite sure I'm not the only one. May I ask you how did you come to these problems, and what do you expect from an answer? Just curious to know if there is something behind, but of course a problem can be worth studying per se. --pma (talk) 09:52, 4 December 2009 (UTC)

I hate to say it, but it just seems like a loose chain of inquiries in pure mathematics. I like asking and trying to answer mathematical questions, I guess. I'm interested in knowing whether high-powered methods I have little access to so far might be useful in answering some questions in this inquiry here, or I don't suppose there would be any point in doing anything but exploring the questions on my own in private until I got the best results I could. Finding that the 1 December question was simple was nice. Inquiry into related questions may result in a research work of some breadth, if not real depth. Or perhaps the questions I'm asking are just hard enough for someone else to be able to make headway where I can't. Early terms in the sequence of this section's first paragraph give seemingly lumpy (big primes) numbers, and perhaps I've hit on something nice. I submitted the analogue of oeis:A168612, I should say to save trouble.

Here is the all-base question for the 1 December question that might be worth looking at: How does {1, 1, 1, 2, ...} continue, where the terms are the coefficients of relatively prime polynomials? [{1, x+1, x²+x+1, 2x³+x²+x+1,...}]/Julzes (talk) 10:23, 4 December 2009 (UTC)

In case anybody reading this is working on the other direction in base two, you can stop. User:PrimeHunter both confirmed--with proof--the first case and determined the full other number. Both are at his talk space.Julzes (talk) 22:33, 5 December 2009 (UTC)

Quick Q about $e^{i\pi }+1=0,\,\!$

So...

$e^{i\pi }+1=0,\,\!$

Can't you do:

$e^{i\pi }=-1\,\!$

$(e^{\pi })^{i}=-1,\,\!$

Substitute $e^{\pi }\approx 23.1406926\,\!$

$(23.1406926)^{i}\approx -1,\,\!$

And then...

$((23.1406926)^{i})^{i}\approx (-1)^{i}\,\!$

$0.0432139183\approx (-1)^{i}\,\!$

???--70.122.122.131 (talk) 10:01, 4 December 2009 (UTC)

no: the problem is that in general $a^{bc}\neq (a^{b})^{c}$ for complex numbers a,b,c. 129.67.37.143 (talk) 10:24, 4 December 2009 (UTC)

More specifically, $\left(a^{b}\right)^{c}$ can have some values that $a^{bc}$ doesn't. $a^{bc}=\exp(bc\log a+2\pi ikbc)\,\!$, while $\left(a^{b}\right)^{c}=\exp(bc\log a+2\pi ikbc+2\pi ilc)$. -- Meni Rosenfeld (talk) 10:36, 4 December 2009 (UTC)

[ec] Exponentiation is an inherently multivalued function. You can sidestep the problems as long as you're dealing only with real numbers, but that becomes harder when you start considering complex numbers.

In fact, Euler's identity is more accurately written $\exp(i\pi )+1=0$, where exp is the exponential function. -1 is just one of the values of $e^{i\pi }$.

But yes, one of the values of $(-1)^{i}$ is indeed $e^{-\pi }\approx 0.0432$. -- Meni Rosenfeld (talk) 10:28, 4 December 2009 (UTC)

There's different rules for exponentiating complex numbers and positive real numbers. A positive real number to a complex power has a unique value. It is only if you consider the real number to be a complex number that it may have other values. You can't use the rules for positive reals on −1 so t has to be treated as a complex number to get a result. Dmcq (talk) 17:19, 4 December 2009 (UTC)

I remember being amused to learn that iⁱ has a real value of something like 0.207. 67.117.130.175 (talk) 20:14, 4 December 2009 (UTC)

That is, quite truly, a realization of the imaginary. --129.116.47.169 (talk) 20:52, 4 December 2009 (UTC)

minima help please

hey great mathematicians at that end i am struck up in a mathematical optimisation problem

actually i have modelled a situation which requires solution of a differential equation by divided differences method.Finally i have arrived at:

dq(i) = A(i)*q(i+1) + B(i)*q(i) + C(i)*q(i-1) + D(i);

with initial condition of q(i)=0 and assumed values of A,B,C,D the equation is solved with ODE45 solver in a specified time domain.

What i am actually trying to do is.I need to minimize dq(i).on plotting solution by ode45 i am getting straight lines(homogeneous) all starting from origin.PLease help.What should be done. yours SCI-hunter (talk) —Preceding undated comment added 10:52, 4 December 2009 (UTC).

Not sure what all this is in aid of. If you set q(i)=0 surely dq(i)=D(i) for all i? Did you mean instead to loop around setting the q(i) using the dq(i)? Dmcq (talk) 18:53, 4 December 2009 (UTC)

Naive or automatic forecasting from multivariate time-series

As an example of the data lets say I want to forecast the unemployment rate in a particular city. I have time-series for the unemployment rates in this and several other nearby cities. I also have time series for things like national unemployment rates, inflation, interest rates etc. Many of these time series will be correlated with each other. Rather than reading some hefty textbooks about time-series and what I think is called 'panel data' and doing it manually, are there any ways of producing a forecast automatically without needing to make human judgements about things? I am interested only in a forecast, I do not care about model-building. I'd prefer no-cost software. Thanks 92.29.42.147 (talk) 14:18, 4 December 2009 (UTC)

Maybe R (programming language) has what you need. Time series are usually tackled with Hidden Markov models or recurrent neural networks. --Ayacop (talk) 18:37, 4 December 2009 (UTC)

You'd have to be more specific about the R language to be helpful. I believe univariate time series are usually tackled with the Box–Jenkins methodology rather than what you said; I don't know what applies to multivariate time series although I've just found out about "panel data" in econometrics but know nothing about it. I'm looking for either or both of a) some 'sausage-machine' software that takes in the data above and automatically outputs a forecast, b) a description of a proceedure(s) (that could be programmed in R perhaps) that does the same thing. Thanks 92.29.42.147 (talk) 00:31, 5 December 2009 (UTC)

I heard today of a program that extracts formulae from data -[1]- why don't you try that? --Ayacop (talk) 18:16, 5 December 2009 (UTC)

You can fit an ARIMA model to the data using the arima() function in the stats package, and then use it to forecast via the predict.Arima() function. That doesn't take into account the other data you have, though, and doesn't allow you to do any kind of intervention analysis to robustify the model parameter estimates. For something with a bit more power, you can use the X-12-ARIMA program produced by the US Bureau of Census. Confusing Manifestation(Say hi!) 04:43, 6 December 2009 (UTC)

The Eurqa program certainly looks interesting, but I'm not sure how many variables are allowed, and the forum suggests that it is buggy, and it may require hours or longer to reach a solution. The ARIMA and X12-ARIMA are univariate, so they don't apply to the multivariate data that I want to use. 78.146.231.126 (talk) 12:42, 7 December 2009 (UTC)

Infinite roots

Obviously (?) the infinith root of any finite real number is 1. But what is the infinith root of infinity? —Preceding unsigned comment added by 79.75.112.56 (talk) 21:47, 4 December 2009 (UTC)

What you really mean by that first statement is $\forall y>0\lim _{x\rightarrow \infty }{\sqrt[{x}]{y}}=1$, which is true. For the latter, you have $\lim _{(x,y)\rightarrow (\infty ,\infty )}{\sqrt[{x}]{y}}=?$, but you have to specify the path along which your point is moving. Without that, it's an indeterminate form. --Tardis (talk) 22:25, 4 December 2009 (UTC)

(ec) Note that the term "infinitith rooth" makes no sense unless you have defined it somehow. More interestingly than trying to give a meaning to it, I'd like to recall that not necessarily every sentence that one can compose automatically makes sense. What is the area of a regular polygon with 3 edges and a half? What is the power series expansion of a hen at 0? &c --pma (talk) 22:34, 4 December 2009 (UTC)

Why is a mouse when it's spinning? --Trovatore (talk) 23:09, 4 December 2009 (UTC)

Because its a rotating rodent? —Preceding unsigned comment added by 79.75.112.56 (talk) 01:04, 5 December 2009 (UTC)

The answer I learned was "the further, the higher". --Trovatore (talk) 01:21, 5 December 2009 (UTC)

OK, so suppose

$\lim _{x\to a}f(x)=\infty \,$

$\lim _{x\to a}g(x)=\infty \,$

and we want

$\lim _{x\to a}{\sqrt[{f(x)}]{g(x)}},\,$

i.e.

$\lim _{x\to a}g(x)^{1/f(x)}.\,$

This is equal to

$\exp \lim _{x\to a}\left({\frac {\ln g(x)}{f(x)}}\right).$

Here I relied on the fact that exp is a continuous function: that justifies putting "exp" outside the "lim", as you see it above, rather than inside.

The numerator and denominator in this fraction both approach infinity. It is each to choose the two functions ƒ and g so as to make that limit equal to 4; likewise to 5, etc. For example, suppose ƒ(x) = x and g(x) = x⁵. Think of L'Hopital's rule.

In other words: this is an indeterminate form; the answer depends on which functions ƒ and g are. Michael Hardy (talk) 23:04, 4 December 2009 (UTC)

To clarify - specifying f and g is equivalent to specifying the path Tardis was talking about. --Tango (talk) 18:06, 5 December 2009 (UTC)

Borel sets

On a recent measure theory homework, I wanted to use the fact that an arbitrary Borel set (in R × R) can be written in terms of a countable collection of open sets using countably many unions, intersections, and complements. To check that I wasn't misunderstanding something, I looked at Wikipedia's Borel set article, and found a sentence under Generating the Borel algebra: "Note: for any fixed Borel set, we only have to iterate a countable number of times…." This seemed to support my claim, which is what I understood a Borel set to be, so I stated my claim as a fact without proof.

Today I got my paper back. That sentence was circled with the comment, "Ach, I don't think this is true," and I lost a couple of points. The professor talked briefly about this at the beginning of class, saying (I think—I must admit I was running late this morning so I missed a bit) that the claim I made does not follow from the definition of the Borel σ-algebra on R × R and calling it a common misunderstanding.

So I'm a little confused. Help? —Bkell (talk) 23:19, 4 December 2009 (UTC)

Can you be a little more specific about what you mean "written in terms of a countable collection..."? The claim is certainly true, for a broad enough sense of the word "written", but it's possible that your further argument assumed some sort of normal form that was too simple. --Trovatore (talk) 23:47, 4 December 2009 (UTC)

Ah, I can see one possible source of confusion: The phrase iterate a countable number of times means that the length of the iteration is some countable ordinal. It definitely does not mean that you only have to do it ω-many times, which is one not-entirely-unreasonable reading of that phrase. Maybe the article needs to be clarified on that point. --Trovatore (talk) 23:54, 4 December 2009 (UTC)

Thank you for your explanation. I'm still having trouble trying to come up with an example of a Borel set that can't be constructed with just ω-many operations, though—it seems like De Morgan's laws could be used to rewrite an expression that used more.

Anyway, the homework question read as follows:

Let ${\mathcal {B}}$ be the σ-algebra of Borel sets in R.

(a) Show that every open set in R × R is in ${\mathcal {B\otimes B}}$. Deduce that ${\mathcal {B\otimes B}}$ is the σ-algebra of Borel sets in R × R.

(b) Let E ⊆ R be a Borel set, and let $A=\{\,(x,y)\in \mathbf {R\times R} :x-y\in E\,\}$. Show that $A\in {\mathcal {B\otimes B}}$.

For part (b) I said the following:

The set E × R is a product of Borel sets, so it is in ${\mathcal {B\times B}}$ (hence in ${\mathcal {B\otimes B}}$). Therefore it can be written in terms of a countable collection of open sets $\{U_{i}\}_{i=1}^{\infty }$ using countably many unions, intersections, and complements.

Now the set A is the collection of all lines of the form y = x − e for e ∈ E, so it is the set obtained from E × R after a rotation by 45° clockwise (and a scaling by a factor of $1/{\sqrt {2}}$). This is the linear transformation T given by the matrix

$M={\frac {1}{\sqrt {2}}}{\begin{bmatrix}\cos(-\pi /4)&-\sin(-\pi /4)\\\sin(-\pi /4)&\cos(-\pi /4)\end{bmatrix}}={\begin{bmatrix}1/2&1/2\\-1/2&1/2\end{bmatrix}}$.

We observe that T : R × R → R × R is bijective (equivalently, M is invertible), so the inverse map T⁻¹ : R × R → R × R exists. Then T⁻¹ is a linear transformation defined on the finite-dimensional (normed) vector space R × R, so it is continuous. Therefore the inverse image of an open set under T⁻¹ is open, i.e., the image of an open set under T is open.

Therefore TU_i is an open set for all i ∈ N. Applying the same sequence of unions, intersections, and complements to the collection $\{TU_{i}\}_{i=1}^{\infty }$ as we used in the representation of E × R in terms of $\{U_{i}\}_{i=1}^{\infty }$, we obtain the set A. So A can be written in terms of a countable collection of open sets using countably many unions, intersections, and complements, which means $A\in {\mathcal {B\otimes B}}$.

—Bkell (talk) 18:18, 7 December 2009 (UTC)

If there's a reasonably simple explicit example of an infinite-rank Borel set, it would be nice to have it in Borel hierarchy. Algebraist 18:26, 7 December 2009 (UTC)

The map F: R×R → R, F(x,y) = x−y, is continuous. — Carl (CBM · talk) 18:41, 7 December 2009 (UTC)

I don't actually recognize this usage of $\otimes$ — what does it mean?

I think your argument is probably correct, read correctly. But you didn't state very clearly what you meant by "written in terms of...", and the prof is probably entitled to doubt that you have a precise meaning in mind. --Trovatore (talk) 19:00, 7 December 2009 (UTC)

${\mathcal {B\otimes B}}$ denotes the σ-algebra generated by ${\mathcal {B\times B}}$. It is true that I didn't have a very rigorous idea of what I meant there, so certainly the points I missed are justified. —Bkell (talk) 19:12, 7 December 2009 (UTC)

Well, here's the outline of a way to make it precise. Consider wellfounded trees, with the root at the top, and where every node has exactly 0, 1, or $\aleph _{0}$ children. Label the leaf nodes with open sets. At the countably splitting nodes, label the parent with the union of the sets labelling its children. At the nodes that don't split, label the parent with the complement of the set labelling its child.

Now the Borel sets are exactly the sets you can get as labels for the root of some such tree. Your argument now works by transfinite induction.

This is exactly how I would go about showing that the continuous preimage of a Borel set is Borel. I'm sure there's some way involving minimality that requires fewer words to state, but this is the way that I find intuitive. --Trovatore (talk) 19:36, 7 December 2009 (UTC)

Details on the minimality argument: if f is continuous the collection of all Borel sets B such that f ^-1(B) is a Borel set, is a sigma algebra containing all open sets, therefore it's the whole collection of Borel sets (for Borel sets are the sigma-algebra generated by the open sets).

As to the initial question: every Borel set can be expressed by means of some countable combination of "union" an "complement" operations, performed over a countable family of open sets. Again, it's true because the collection of all such Borel sets includes all open sets, and it is a sigma algebra (just because the set of these operations is closed under composition with the operation "union" and with the operation "complement"). The important issue, as Trovatore remarks, is that such set of operations you have to consider is possibly uncountable. To clarify better the procedure, you can introduce an increasing family $\scriptstyle {\mathcal {B}}_{\alpha }$ of sets, indexed over all ordinals α≤ω₁, similarly to the link. So $\scriptstyle {\mathcal {B}}_{0}$ is the family of open sets; $\scriptstyle {\mathcal {B}}_{\alpha +1}$ is made by all countable unions and complements of the sets in $\scriptstyle {\mathcal {B}}_{\alpha };$ and for limit α $\scriptstyle {\mathcal {B}}_{\alpha }$ is the union of all $\scriptstyle {\mathcal {B}}_{\beta }$ with β<α. The class $\scriptstyle {\mathcal {B}}_{\omega _{1}}$ is then a sigma algebra: any countable family (A_i) in $\scriptstyle {\mathcal {B}}_{\omega _{1}}$ is such that $A_{i}$ is in some $\scriptstyle {\mathcal {B}}_{\alpha _{i}}$ for some countable ordinal α_i, so the union of the $A_{i},$ and its complement is in $\scriptstyle {\mathcal {B}}_{\alpha }$ with $\scriptstyle \alpha :=\sup _{i}\alpha _{i}+1<\omega _{1}$, hence in $\scriptstyle {\mathcal {B}}_{\omega _{1}},$ which is therefore a sigma algebra, in fact the Borel sigma algebra. --pma (talk) 14:53, 9 December 2009 (UTC)

Well, the number of operations you need to get a particular Borel set is countable. But the point I was making was that the length of the iteration, although countable, can be a countable ordinal larger than ω. It wasn't clear to me what form exactly Brian had in mind when he spoke of "writing" the set in terms of countably many open sets, but I suppose he might have thought, say, that it could always be written as a countable union of finite-rank Borel sets, or something like that. That would be incorrect.

But it's quite correct that for any particular Borel set, there is a representation that involves only countably many open sets to start with, to which you apply countably many operations of union and complement. It's just that the order in which you do the operations might make the process longer than ω. --Trovatore (talk) 03:30, 10 December 2009 (UTC)

Paper folding

Is there a theoretical or practical limit to the number of times a piece of paper can be folded in half? Why does this limit exist? —Preceding unsigned comment added by 79.75.112.56 (talk) 23:30, 4 December 2009 (UTC)

Yes. Atoms. --COVIZAPIBETEFOKY (talk) 23:45, 4 December 2009 (UTC)

Britney Gallivan did a well known experiment about this, and wrote up some of the relevant theory. 67.117.130.175 (talk) 00:44, 5 December 2009 (UTC)

An article called Paper folding has a bit about this. Dmcq (talk) 00:47, 5 December 2009 (UTC)

It's mostly to do with the radius of the fold. The mathematics isn't difficult - I haven't read her write-up but I spent about an hour and was able to replicate Ms. Gallivan's result. What most puzzles me is that given the simplicity of the answer, why did no one come up with it before? Thinking about my own experience, I was always told that more than seven folds were impossible due to something at atomic level. I'd always assumed that this must have been proved at some point - it never occurred to me that this could be wrong. Is this just a case of misinformation running riot? Readro (talk) 11:51, 7 December 2009 (UTC)