Revision as of 02:45, 6 September 2012

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

• WP:RD/MA

Main page: Help searching Misplaced Pages

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

How do I answer a question?

Main page: Misplaced Pages:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

• Teahouse
• Help desk
• Village pump
• Help manual

August 30

Every nonfinitely generated abelian group must contain one of... (resumed)

I asked this question, and got one useless response (that misunderstood the question). Here it is my question, slightly revised to clarify, and my attempt to answer my own question.

Is there any list of relatively simple nonfinitely generated abelian groups, such that any arbitrary nonfinitely generated abelian group must contain one of the groups in the list as a subgroup?

An attempt to answer my own question. I believe the following is such a list, except I'm unsure about the last point. Let ${\displaystyle A}$ be an abelian group:

Case 1: ${\displaystyle A}$ contains an infinite sequence of divisible elements, ie, a sequence ${\displaystyle x_{1},x_{2},\cdots }$ such that ${\displaystyle \langle x_{i}\rangle \subsetneq \langle x_{i+1}\rangle }$. Then ${\displaystyle \langle x_{1},x_{2},\cdots \rangle }$ is isomorphic to a subgroup of ${\displaystyle \mathbb {Q} }$ or ${\displaystyle \mathbb {Q} /\langle 1\rangle }$.

Case 2: ${\displaystyle A}$ does not contain such an infinite sequence, and its torsion group is not finitely generated. Then by CRT, only finitely many primes occur as the order of some element, because otherwise every finite order element is divisible. One of those primes must occur infinitely often, because the elements of order ${\displaystyle p^{i}}$ generate the torsion subgroup, again by CRT, and if, for such a prime ${\displaystyle p}$, there are only finitely many elements of order ${\displaystyle p}$, then it's not to difficult to show, using the classification of finitely generated abelian groups, that there must be an element of order ${\displaystyle p}$ which begins a sequence of the form in case 1. Then countably infinitely many elements of order ${\displaystyle p}$ generate a vector space over ${\displaystyle \mathbb {F} _{p}}$ of countably infinite dimension - ie, ${\displaystyle \left(\mathbb {Z} /p\mathbb {Z} \right)^{\aleph _{0}}}$.

Case 3: Otherwise, must ${\displaystyle A}$ necessarily contain a direct sum of countably many copies of ${\displaystyle \mathbb {Z} }$?

Thanks for anyone who happens to know, or be able to work through the math and make any additional arguments necessary! --70.116.7.160 (talk) 14:01, 30 August 2012 (UTC)

The answer to the “Case 3” question is no: for any finite n > 1, there are infinitely generated torsion-free abelian groups of rank n with no infinitely generated subgroup of smaller rank (which in particular implies that there is no infinite descending divisor chain). For a concrete example, consider the subgroup of ${\displaystyle \mathbb {Q} ^{2}}$ generated by ${\displaystyle \mathbb {Z} ^{2}}$ and by the elements ${\displaystyle (2^{-m},\sum _{k^{2}<m}2^{k^{2}-m})}$, ${\displaystyle m\in \mathbb {N} }$. (The general pattern is given below, (6).)

I don’t have the time now to write a detailed proof, but I will sketch a (hopefully) complete classification. Let A be an infinitely generated abelian group:

• First, assume that its torsion subgroup ${\displaystyle A^{tor}}$ is infinite (= infinitely generated). If the p-torsion subgroup A_p is nontrivial for infinitely many p, then A contains a subgroup isomorphic to

${\displaystyle (1)\qquad \bigoplus _{p\in I}\mathbb {Z} /p\mathbb {Z} ,}$

where I is an infinite set of primes. Otherwise, A_p is infinite for some prime p. If there are infinitely many elements of order p, then A contains

${\displaystyle (2)\qquad (\mathbb {Z} /p\mathbb {Z} )^{(\omega )}}$

(the direct sum of countably many copies of ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$). Otherwise, for every ${\displaystyle x\in A_{p}}$ there are only finitely many ${\displaystyle y\in A_{p}}$ such that ${\displaystyle x=py}$; since A_p is infinite, König’s lemma implies that there is an infinite chain ${\displaystyle \{x_{n}:n\in \omega \}\subseteq A_{p}}$ such that ${\displaystyle x_{0}=0}$, ${\displaystyle x_{1}\neq 0}$, and ${\displaystyle px_{n+1}=x_{n}}$. Then ${\displaystyle \langle x_{n}:n\in \omega \rangle }$ is isomorphic to the Prüfer group

${\displaystyle (3)\qquad \mathbb {Z} (p^{\infty }).}$

• The other case is that ${\displaystyle A^{tor}}$ is finite. Then ${\displaystyle A/A^{tor}}$ is an infinitely generated torsion-free group. In fact, by successively chosing suitable elements ${\displaystyle x_{n}\in A}$ such that ${\displaystyle x_{n}}$ is not in ${\displaystyle \langle x_{i}:i<n\rangle +A^{tor}}$, one can show that A itself includes an infinitely generated torsion-free subgroup. Thus, we can assume without loss of generality that A is torsion-free.

If A has infinite rank, its injective envelope is a vector space over ${\displaystyle \mathbb {Q} }$ of infinite dimension. If we choose an infinite linearly independent set, which we may assume to lie in A, we see that A contains a copy of

${\displaystyle (4)\qquad \mathbb {Z} ^{(\omega )}.}$

If A has finite rank, let n be the minimal rank of its infinitely generated subgroup. We may assume that A itself has rank n. Its injective envelope is a ${\displaystyle \mathbb {Q} }$-vector space of dimension n, and A includes n linearly independent elements, hence we may assume that ${\displaystyle \mathbb {Z} ^{n}\subseteq A\subseteq \mathbb {Q} ^{n}}$. The quotient ${\displaystyle A/\mathbb {Z} ^{n}}$ is an infinite torsion group contained in ${\displaystyle (\mathbb {Q} /\mathbb {Z} )^{n}}$, hence by the previous part, it contains a copy of (1) or (3). In the former case, A contains a subgroup of ${\displaystyle \mathbb {Q} ^{n}}$ of the form

${\displaystyle (5)\qquad \mathbb {Z} ^{n}+\langle p^{-1}a_{p}:p\in I\rangle ,}$

where I is an infinite set of primes, and for each ${\displaystyle p\in I}$, ${\displaystyle a_{p}\in \mathbb {Z} ^{n}}$ is such that not all coordinates of a_p are divisible by p. Moreover, all infinitely generated subgroups of this group have rank n; one can show that this condition is equivalent to the statement that for every linear function ${\displaystyle L(x_{1},\dots ,x_{n})=\sum _{i}m_{i}x_{i}}$, where ${\displaystyle m_{i}\in \mathbb {Z} }$ and ${\displaystyle \gcd(m_{1},\dots ,m_{n})=1}$, there are only finitely many ${\displaystyle p\in I}$ such that ${\displaystyle L(a_{p})\equiv 0{\pmod {p}}}$. In particular, we may assume that all coordinates of every a_p are coprime to p.

The remaining case is that ${\displaystyle A/\mathbb {Z} ^{n}}$ includes a copy of ${\displaystyle \mathbb {Z} (p^{\infty })}$. Let ${\displaystyle \mathbb {Z} _{p}}$ denote p-adic integers, and ${\displaystyle \mathbb {Q} _{p}}$ its fraction field of p-adic numbers. For ${\displaystyle a=\sum _{i=k}^{\infty }a_{i}p^{i}\in \mathbb {Q} _{p}}$, let me write ${\displaystyle \mathrm {Frac} (a)=\sum _{i=k}^{-1}a_{i}p^{i}}$, so that ${\displaystyle a-\mathrm {Frac} (a)\in \mathbb {Z} _{p}}$ and ${\displaystyle \mathrm {Frac} (a)\in \mathbb {Z} \subseteq \mathbb {Q} }$. Moreover, if ${\displaystyle a\in \mathbb {Q} _{p}^{n}}$, I’ll write ${\displaystyle \mathrm {Frac} (a)}$ for the coordinate-wise application of Frac. Using this notation, it is not hard to show that A contains a subgroup of ${\displaystyle \mathbb {Q} ^{n}}$ of the form

${\displaystyle (6)\qquad \mathbb {Z} ^{n}+\langle \mathrm {Frac} (p^{-k}a):k\in \omega \rangle ,}$

where ${\displaystyle a\in \mathbb {Z} _{p}^{n}}$. Again, additionally all infinitely generated subgroups of this group have rank n, which is equivalent to the condition that the n coordinates of a, as elements of ${\displaystyle \mathbb {Q} _{p}}$, are linearly independent over ${\displaystyle \mathbb {Q} \subseteq \mathbb {Q} _{p}}$.

Note that for n = 1, cases (5) and (6) reduce to the groups ${\displaystyle \mathbb {Z} +\langle p^{-1}:p\in I\rangle }$ and ${\displaystyle \mathbb {Z} }$, respectively, which, as subgroups of ${\displaystyle \mathbb {Q} }$, belong to your Case 1. However, for n > 1 the groups are new.—Emil J. 13:28, 3 September 2012 (UTC)

Thanks! I think I understood the first half of your classification perfectly, and I'll need to do a bit of research to get the background to pin down the latter parts of it. --70.116.7.160 (talk) 20:22, 3 September 2012 (UTC)

August 31

volume

What is the volume (ounces or mls) in a fifth of whiskey? — Preceding unsigned comment added by 71.182.193.144 (talk) 00:33, 31 August 2012 (UTC)

It depends on the mixture, the temperature, the altitude of the sample and your position on the Earth. Moreover, it depends on the orbit of the Earth around the Sun, and on the Sun's motion through our galaxy. All of these things affect the volume. — Fly by Night (talk) 00:57, 31 August 2012 (UTC)

How density varies would only matter if a fifth was a unit mass. It is not, it's a unit of volume. See below. Therefore, if the number of fifths goes up for a given mass, so does the number of ounces and milliliters, in proportion, such that the number of ounces or milliliters in a fifth remains constant. (Note that I didn't engage in a personal attack just because you gave a poor answer.) StuRat (talk) 02:20, 31 August 2012 (UTC)

Not a personal attack, but a plain statement of fact - the first response was inappropriate, being patronising, belittling and worst of all, plain wrong. If you can't give an accurate, polite and helpful answer then don't give any.←86.139.64.77 (talk) 20:46, 1 September 2012 (UTC)

See Fifth (unit). hydnjo (talk) 01:00, 31 August 2012 (UTC)

Solving a summation

I don't have the math background to know where to start with this. I have a summation of the usual sort with n on the top and i=0 on the bottom... and then the actual summation formula itself is a constant with i as an exponent. The problem is, I don't want to know what the answer is at a given n, I want to know what n is when I reach a given constant. I want to solve for the n. How do I go about figuring this out? Broba (talk) 07:42, 31 August 2012 (UTC)

Here's a simpler example of what I'm trying to do to illustrate the basics of what I can't figure out: Summation with i=0, the formula inside the summation is 3 * i. I want to know at what value of n the summation equals 18. What's the method you use to arrive at the value of n? Is it possible to do the same if the summation equals say 17? Broba (talk) 07:47, 31 August 2012 (UTC)

Quite simple to do with a computer program, although your example is easy enough to do by hand:

i  3i   ∑
---------
0   0   0
1   3   3
2   6   9
3   9  18

So we don't get 17 for the summation, assuming n is an integer. I don't think non-integer solutions for n (like n = 8/3) make sense in a summation, since, if you add in i = 8/3, how can you justify not adding in i = 7/3, as well, along with the infinite number of other non-integers ? StuRat (talk) 07:58, 31 August 2012 (UTC)

Well, another way to do something like this would be to close form solution of the summation as a function of n (if possible) and then setting it equal to whatever number you want (17 in this case) and solving for n. Like StuRat said, there is no guarantee if n would be a natural integer or not. Are you looking only for natural integers? To illustrate with your example, let ${\displaystyle f(n)=\sum _{i=0}^{n}3i={\frac {3n(n+1)}{2}}}$. Then you want to solve for n where ${\displaystyle {\frac {3n(n+1)}{2}}=17}$ and in this case we have a simple quadratic and the answer is ${\displaystyle n={\frac {-3+{\sqrt {417}}}{6}}=2.90343...}$. There is another solution too which is negative which we ignore. As you can see this is close to n=3 which would give us the sum equals 18. Is this what you are kind of looking for? Someone here might be able to help you furthermore if you give us the sum and how/where this problem arises.68.121.32.26 (talk) 10:32, 31 August 2012 (UTC)

But are non-integer solutions actually allowed in a summation ? To me it doesn't make any sense. As I noted before, if you sum in one non-integer value (the final one), then you would have to sum in all non-integer values, wouldn't you ? This would typically mean the solution is either positive infinity or negative infinity, regardless of n, which isn't very useful. StuRat (talk) 20:22, 31 August 2012 (UTC)

For an exponential function, use ${\displaystyle \sum _{i=0}^{n-1}a^{i}={\frac {1-a^{n}}{1-a}}}$ Ssscienccce (talk) 15:27, 31 August 2012 (UTC)

Thank you both 68.121.32.26 and Ssscienccce. That is the approach I'm trying to take, although I think my problem has additional complexities. What is the name of this sort of math... I had a lot of trouble knowing what to search for for this.

The complications I have is that I tried to use the exponential function that Ssscienccce gave but I have some coefficients that I believe are screwing it up. Non integers are fine (expected probably). This is specifically the form of the problem I'm trying to solve (and yes I could estimate it with a program, I'm not interested in that... I'm looking for the method to arrive at the answer more than any specific answer):

${\displaystyle \sum _{i=0}^{n}100e^{0.05n}=5000}$

I'm trying to solve for ${\displaystyle n}$ here of course. As an aside, I have a hunch there's some analogy to this kind of problem in physics but I haven't grasped exactly which yet. Broba (talk) 17:47, 31 August 2012 (UTC)

Oh I got it now. I just found another version of Ssscienccce's explanation with coefficients. Thanks for you help. Broba (talk) 21:56, 31 August 2012 (UTC)

Didn't you mean ${\displaystyle \sum _{i=0}^{n}100e^{0.05i}=5000}$ ? Bo Jacoby (talk) 06:56, 1 September 2012 (UTC).

Late to the party but whatever... If you can still use some advice, I try to walk you step by step to the solution. Some things, like the 100 make your equation look far more formidable than it really is. I'll compute the "a" for you but only outline the later steps, it's quite straightforward once you see what to compute, and last but not least, I'm doing the stuff mentally atm.

Let's look at your sum of 100exp(0.05i) = 5000. You can cancel out a factor of 100 to get "Sum of exp(0.05i) = 50", and now assume that a = exp(0.05) = 1.051..., so this is a fancy way to write "Sum of a^i = 50".

Ssscienccce's formula gives you a closed form for that kind of summation. Multiply by (1-a) to get something like "1 - foo^bar = 50 (1-a)", add foo^bar, and subtract the constants on the right-hand side to get something like "constant = foo^bar,"

something you can attack with a log operation to get "bar = _foolog(constant)". Sorry for the sloppy terminology.

- ¡Ouch! ( / _{more pain}) 07:23, 3 September 2012 (UTC)

compare all to all

I have a set S and I want to compare every item in S to every other item in S. The comparison is a simple function like f(S1,S2). I claim that it is impossible to do this without S*(S-1) comparisons. I've been told it can be done with S*log(S) comparisons, but not how it can be done that way. Can anyone explain to me how that is possible? — Preceding unsigned comment added by 128.23.113.249 (talk) 14:29, 31 August 2012 (UTC)

Use any of the worst-case ${\displaystyle n\log n}$ comparison sorts from the table in sorting algorithm#Comparison of algorithms, such as merge sort. Once you sort the set, you can compare any two items by comparing their index in the sorted set without invoking f. This all assumes that f is a bona fide total order.—Emil J. 14:41, 31 August 2012 (UTC)

Please correct me if I'm wrong, but that implies that S is sortable. I'm trying to come up with an example that shows how they are not sortable based on f. What if you have a set of people S. Then f(S1,S2) is a rating of how much S1 likes S2. We can make it simple and assume f(S1,S2)=f(S2,S1) if that is important. Then, you have a weighted graph where each node is an element in S and the edges have a weight, the value of f for the two nodes. If I use f to sort S with, say, merge sort, I won't compare every element in S to every other element and, therefore, will be missing edges in my graph. Does that make sense or am I just rambling nonsense? — Preceding unsigned comment added by 128.23.113.249 (talk) 14:59, 31 August 2012 (UTC)

Your f is not a comparison function (i.e., an indicator function of a total (pre)order). If you allow a completely arbitrary function as f, then there is of course no way of finding all its values for all pairs of elements other than checking all the |S| pairs.—Emil J. 15:37, 31 August 2012 (UTC)

Thank you. I believe our class argument is actually an argument about how f is defined, not about the set S. It all depends on if f defines total order or just some arbitrary relationship between two items. — Preceding unsigned comment added by 128.23.113.249 (talk) 15:42, 31 August 2012 (UTC)

You may want to check out Closest pair of points problem Ssscienccce (talk) 16:19, 31 August 2012 (UTC)

solutions to an assignment

Hello I am an independent learner looking through material here: http://www.hutter1.net/ethz/uaiethz.htm and in particular trying the assignment here: http://www.hutter1.net/ethz/assign1.pdf but sadly there are no solutions to this assignment on that website. Some questions are easy math questions but some are hard. Could someone kind create solutions or refer to elsewhere? — Preceding unsigned comment added by Bulkc (talk • contribs) 18:05, 31 August 2012 (UTC)

That's a bit much to ask of us, I'm afraid. We also won't do your homework for you. However, if you do it, and post your answers here, we might be willing to check it for you and point out any mistakes. StuRat (talk) 20:28, 31 August 2012 (UTC)

Ok. The first two questions and the probability questions are easy any way. I think I can do too the question MDL-ML, part (i) of MDL-Ber and some of KC-KC myself. What about the rest? For example can you show me how to do KC-KC part (iv) which does not follow from the rest I think. Or inequality K(xy) < K(x,y) — Preceding unsigned comment added by Bulkc (talk • contribs) 20:51, 31 August 2012 (UTC)

For (iv), let ${\displaystyle T}$ be the machine that, on input ${\displaystyle a}$, first runs ${\displaystyle U(a)}$. Then, if the output is a pair ${\displaystyle (x,f)}$, runs ${\displaystyle f}$ on ${\displaystyle x}$ and outputs ${\displaystyle f(x)}$. Now, if ${\displaystyle U(a)=(x,f)}$, then ${\displaystyle T(a)=f(x)}$. This shows that ${\displaystyle K_{T}(f(x))\leq K(x,f)}$, which is less than ${\displaystyle K(x)+K(f)}$ by part (iii). Since ${\displaystyle K\leq ^{+}K_{T}}$, the result follows.

For ${\displaystyle K(xy)\leq ^{+}K(x,y)}$, let ${\displaystyle T}$ be the machine that, on input ${\displaystyle a}$, first runs ${\displaystyle U(a)}$. Then, if the output is a pair ${\displaystyle (x,y)}$, ${\displaystyle T}$ outputs ${\displaystyle xy}$. Then follow the same reasoning as above.--121.73.35.181 (talk) 00:08, 1 September 2012 (UTC)

Thank you! I can do now these questions, and some other ones, due to your advice about Turing machines. But, I am still having some trouble. What about AP-CM (ii) and (iii)? Or MDL-Ber (iii), (v) and (vi)?--Bulkc (talk) 06:14, 1 September 2012 (UTC)

Actually, I just did MDL-Ber (v) using (iv)! — Preceding unsigned comment added by Bulkc (talk • contribs) 06:32, 1 September 2012 (UTC)

Woops, had one of my inequalities backwards. Fixed.--121.73.35.181 (talk) 10:28, 1 September 2012 (UTC)

• After much work and reading through the material, I think I can solve all questions except for AP-CM. I think this is hardest. — Preceding unsigned comment added by Bulkc (talk • contribs) 02:58, 2 September 2012 (UTC)

Here's (i): Fix ${\displaystyle \epsilon >0}$. Let ${\displaystyle A_{t}}$ be the set of infinite sequences ${\displaystyle x}$ with ${\displaystyle M(0|x_{<t})-\mu (0|x_{<t})>\epsilon }$. Note that ${\displaystyle \sum _{t}\mu (A_{t})\epsilon ^{2}}$ is less than the sum in theorem 4.5, so in particular is finite. So ${\displaystyle \sum _{t}\mu (A_{t})}$ is finite, and thus ${\displaystyle \limsup _{t}A_{t}}$ has ${\displaystyle \mu }$-measure 0. This contains all sequences where the limit is infinitely often above ${\displaystyle \epsilon }$. Union over all rational ${\displaystyle \epsilon }$ to get the set of all sequences where the limit is non-zero, and it still has ${\displaystyle \mu }$-measure 0.--121.73.35.181 (talk) 22:40, 2 September 2012 (UTC)

Thank you very much for your help. Let me just ask for solutions to the ones that I'm still not wholly sure about:

KC-Cmp (i)

AP-RC, especially inequality ${\displaystyle K(x|l(x)){\stackrel {+}{<}}KM(x)}$

AP-CM (ii), (iii), and maybe (iv) but I think I can figure to do that one.

I think I would like solutions to all of KC-KC too because I find Kolmogorov complexity confusing still. --Bulkc (talk) 22:56, 4 September 2012 (UTC)

September 1

Konig's lemma

In the proof of Konig's lemma it is mentioned that:

König's lemma may be considered to be a choice principle; the first proof above illustrates the relationship between the lemma and the axiom of dependent choice. At each step of the induction, a vertex with a particular property must be selected. Although it is proved that at least one appropriate vertex exists, if there is more than one suitable vertex there may be no canonical choice.

In the proof mentioned, it is clear that there are only finitely many such vertices to consider at any given stage.(Cf: "Every one of the infinitely many vertices of G can be reached from v1 with a simple path, and each such path must start with one of the finitely many vertices adjacent to v1."..."We may thus pick one of these vertices and call it v2." That is, the choice is being made among finitely many vertices. Why then do we need the axiom of choice or some weaker version of it to prove the lemma? Thanks--Shahab (talk) 13:07, 1 September 2012 (UTC)

I am not at all well up on this, but I believe it is because we are making infinitely many such choices. I do know that (because there is no uniform way of telling a left sock from a right sock, unlike for shoes) you need choice to get one sock from each of infinitely many pairs (apart, of course, from the fact that they are in a nice Euclidean space...) Straightontillmorning (talk) 13:39, 1 September 2012 (UTC)

Yep. You need choice to make infinitely many choices; it doesn't matter whether each of those choices is from finitely or infinitely many possibilities.--121.73.35.181 (talk) 21:02, 1 September 2012 (UTC)

This is a complete guess: if there's only one suitable vertex, you can identify it by trying out paths of increasing length for every vertex. If only one is suitable, this search will end eventually. If more then one is suitable, it won't. Ssscienccce (talk) 14:59, 1 September 2012 (UTC)

September 2

Graph theory

How many trees are there with n vertices such that each vertex has degree at most 4, if ones that are the same other than the naming of the vertices are excluded? --168.7.237.248 (talk) 04:08, 2 September 2012 (UTC)

By working out the first few terms by hand and searching the OEIS, I found A000602. -- BenRG (talk) 06:06, 2 September 2012 (UTC)

What's the closed form for that sequence? --128.42.223.234 (talk) 16:03, 2 September 2012 (UTC)

I don't know. The OEIS entry links to some unreadable Maple code. -- BenRG (talk) 21:00, 3 September 2012 (UTC)

The answer would depend on the meaning of a tree—whether you consider a tree as defined in a graph theory (i.e. undirected connected graph with no cycles) or as defined in computer science (a connected directed graph with a specific root and a transitive is-a-child relation, in which every node is a child of exectly one parent, except a root which has no parent). In the latter case also decide whether to consider (or not) specific ordering of children (is a root with a single left child equivalent to the root with a single right child etc.).
Anyway I do not know the answer in any case. --CiaPan (talk) 05:35, 5 September 2012 (UTC)

PS. Is this problem related to classifying carbon chain structures of organic compounds in organic chemistry? (e.g. IUPAC nomenclature of organic chemistry) CiaPan (talk)

Maths and music

Hi. First of all, I want to acknowledge that the following is homework. However, I've come here because I actually don't understand the problems:

1. I'm asked to find the continued fraction for ${\displaystyle \log _{2}(3/2)}$, calculate convergents ${\displaystyle {\frac {p_{n}}{q_{n}}}}$, and then find the first ${\displaystyle q_{n}>12}$. That's all fine: ${\displaystyle q_{n}=29}$. But then "Compute the relative frequency of the fifth harmonic in equal temperament in this scale with ${\displaystyle q_{n}}$ semitones and compare to the error to 3/2 to that of our usual scale with 12 semitones." I don't understand any of this. I've tried reading a few Misplaced Pages articles, but it still makes no sense to me; I have no musical background.
2. And I have no idea where to begin with this one: "When building a guitar it is useful to be able to determine where to put fret i in relation to fret i + 1. Find the numerical value of the ratio of the length of the string remaining when pressing down at fret i to the distance of fret i to fret i + 1, assuming the usual 12 semitone scale and equal temperament."

Can anyone give some advice on these questions? As I said, I've tried reading a few articles, but the musical terminology is lost on me. I'd appreciate it if someone could distill these problems into a more pure mathematical form, or – just as helpfully – explain in very simple terms the music theory I need to know to comprehend them. PS: I have quoted these questions verbatim. Feeling like they're grammatically incorrect? You and me both. —Anonymous Dissident 13:36, 2 September 2012 (UTC)

What does "the first ${\displaystyle q_{n}>12}$" mean? Please, write down something like log₂ 3/2 =(some fraction with p and q). Incnis Mrsi (talk) 14:50, 2 September 2012 (UTC)

Surely that means "the value of ${\displaystyle q_{n}}$ for the least n such that this is more than 12" (I don't know continued fractions.) However, I do know what 12-semitone equal temperament is so I'll try to be helpful. Musical intervals, in terms of frequencies, are ratios. An octave corresponds to doubling the frequency. In an octave under the standard system there are 12 semitones (A-A#-B-C-C#-D-D#-E-F-F#-G-G#-A), and equal temperament divides them equally (in a logarithmic sense), so that going up a semitone is multiplies the frequency by the twelfth root of two. Presumably you are considering a twenty-nine semitone equally tempered scale so going up a semitone is multiplying by the twenty-ninth root of two. Then for the fifth harmonic, I think we're looking at perfect fifths. I can't make out harmonic series (music), but the former says that the "just" interval for a perfect fifth is 3/2 (ie the frequency goes up by that factor). In equal temperament, it's a bit wrong (because the twelfth root of two is ugly) - I don't see where the fifth harmonic comes in. For the second question, Guitar#Frets says that changing by one fret changes by a semitone. By virtue of the assumption of twelve-tone equal temperament, that means the frequency changes by (a factor of) the twelfth root of two. If you (like I was) are having trouble with parsing the sentence we want the ratio of the (remaining string when you press at the i'th fret) to the (distance between the i'th and (i+1)'st). So you need to assume frequency f for the ith fret, work out how long the string needs to be, work out how long it needs to be for the next note, and hope f cancels.

I hope that helps slightly, but it probably won't. Straightontillmorning (talk) 16:09, 2 September 2012 (UTC)

I think when they say "fifth harmonic" they must be really mean the perfect fifth, since they ask to compare the ratio to 3/2. In that case all the question is asking is to compare 2 to 3/2 and then compare 2 to 3/2. Rckrone (talk) 23:58, 2 September 2012 (UTC)

"fifth harmonic" may really mean fifth harmonic, or rather the major third; the history of musical temperament can be seen as a series of attempts to express 4:5 with factors of 2 and 3. So here's my paraphrase the first question: Using the method of continued fractions, find the next rational approximation to lg(3/2) after 7/12, and discuss the quality of major thirds in the equally-tempered scale implied by that ratio. (I don't get 17/29; I get 24/41 and then 31/53 – but never mind, maybe you used a slightly different form of the CF, and you ought to get 41 next!) So: what is 2 or 2? —Tamfang (talk) 04:35, 3 September 2012 (UTC)

Reading Perfect_fifth#The_pitch_ratio_of_a_fifth, I would interpret "compare to the error to 3/2 to that of our usual scale with 12 semitones" as: for 12 semitones you get 1200*ln(1.5)/ln(2)=701.995 or 2% of a semitone wider than semitone 7; for 29 semitones it's 2900*ln(1.5)/ln(2)= 1696.39... 3.6% of a semitone different from semitone 17. But I've got no idea what the "relative freq of the 5th harm" would mean; relative to what, a semitone? Ssscienccce (talk) 05:34, 3 September 2012 (UTC)

Relative to the tonic. —Tamfang (talk) 23:15, 3 September 2012 (UTC)

In guitar tuning, there are subtleties in frettage that I don't understand, and you're probably not expected to understand either. The simple version is that the frets are placed so that the lengths of a given string from the bridge to each fret form a geometric sequence, whose ratio is (usually) the twelfth root of two. Note that you're not asked for the length of the string, though. —Tamfang (talk) 04:45, 3 September 2012 (UTC)

Scale (string instruments) has the details; lets call a=${\displaystyle \scriptstyle {\sqrt{2}}}$ for short; P(i+1)=P(i)/a , you need Pi/(Pi-P(i+1)) = Pi/(Pi-Pi/a) = ... = a/(a-1) = 17.817 Ssscienccce (talk) 06:30, 3 September 2012 (UTC)

Are you sure about 29? I get: , calculate it till 23: 1/(1+1/(1+1/(2+1/(2+1/(3+1/(1+1/(5+1/(2+1/23)))))))) = 0.5849625024, and 2^0.584... gives me 1.500000002 Dooh! I should learn to read.. Ssscienccce (talk) 06:58, 3 September 2012 (UTC)

Binomial process

I have a closed population which is subjected to a hazard which removes them from the population. I am modelling the number removed each month using a binomial distribution with a constant percentage hazard rate. What is the distribution of the cumulative number of removals after the first T months? I don't necessarily need an exact distribution - the population is large enough that a normal approximation should be sufficient for my purposes. Is it as simple as a mean of n*(1-(1-p)^T) and a variance of n*(1-(1-p)^T)*(1-p)^T? I know it is that simple for a Poisson process, but I suspect it doesn't work the same way for a Binomial. Thanks for your help. --Tango (talk) 17:25, 2 September 2012 (UTC)

I don't think it's a question of Poisson versus binomial. My intuition is that with a constant percentage hazard rate, the strong law of large numbers should give you a log-normal distribution in the limit of large T. Looie496 (talk) 17:46, 2 September 2012 (UTC)

Thanks, but I should have said, T is quite small. For a Poisson, the absolute rate is constant, so you can just scale it. In this case, the rate is reducing because n is reducing, so I doubt it is so simple. --Tango (talk) 18:17, 2 September 2012 (UTC)

Any single individual will have a probability of survival equal to (1-(1-p)^T). And this will be independent from all other individuals. So the whole T months period for all individuals will be n independent trials with sucess chance (1-(1-p)^T). This means that the number of survivors will be Binomially distributed with mean and variance as given in original post. Taemyr (talk) 21:24, 2 September 2012 (UTC)

Of course it is - I was over complicating the whole thing. Thanks! --Tango (talk) 21:36, 2 September 2012 (UTC)

Stone Cetch Compactification using ultrafilters

Hello, In this topology, I saw in a proof that: ${\displaystyle x\in {\overline {\cup A}}}$ and ${\displaystyle x\in {\overline {\cup B}}}$ implies that ${\displaystyle (\cup A)\cap (\cup B)\neq \emptyset }$. Can somone explain why this is true? since, this claim is not true in topology in general... Thanx. — Preceding unsigned comment added by General Topology (talk • contribs) 18:32, 2 September 2012 (UTC) General Topology (talk) 18:43, 2 September 2012 (UTC)

If I understand from your mention of ultrafilters and such, you are talking about the Stone–Čech compactification of a discrete space X, is that right? In that case, the compactificaiton of X is equivalent to the Stone Space of the set of all subsets of X. For x a subset of X let b(x) be all ultrafilters of X containing x, then {b(x) : x} is a basis. It's obvious, then, that for every open set U there is a collection Y of subsets of X so that U is the collection of ultrafilters meeting Y. So, in your case, given collections of ultrafilters A and B, it follows cl(A) is exactly the ultrafilters made from sets in TA, similarly for cl(B). Thus, Tcl(A) = TA and the result follows. Two quick notes: since you didn't say what A was exactly, I'm guessing that A is a set of uf's and that you meant to write union(closure A) not closure(union A), I'm sorry if I'm wrong; I haven't thought about this in a while and am just working this out in my head, so I apologize if there is any stupidity in my answer. :-) Phoenixia1177 (talk) 22:43, 2 September 2012 (UTC)

Hi:) yes, I ment the Stone–Čech compactification of a discrete space X. I have a problem with some convergence properties of this space. Let me try and ask a slightly different question. From what I understand, this space is not Frechet Urysohn (a topological space is frechet urysohn if for every ${\displaystyle x\in {\overline {A}}\setminus A}$ there is a sequence of points in A that converges to x). Can anyone tell why?? General Topology (talk) 11:31, 4 September 2012 (UTC)

I'm working this out on a pad of sketch paper at work, so I apologize for any stupidity. That said, via our above basis, if a(n) is a sequence of ultrafilters, then a(n) converges to a iff for every b in a there is an n(b) so N >= n(b) implies b is in a(N). Now, let X be infinite and a(n) be a nontrivial sequence converging to a, an ultrafilter. Well order a and define F(N) to be the least element larger than everything in {b : n(b) <= N}. Clearly, F(n(b)) >= b for any b, thus, F has to have an unbounded subsequence. However, by Easton's Theorem, the cofinality of a must be larger than the cardinality of X In other words, since X is, at least, countable, we cannot have an unbounded sequnce in a, thus, there can be no nontrivial convergent sequences; which answers your question:-) Phoenixia1177 (talk) 06:28, 5 September 2012 (UTC)

A simpler proof would be to observe that the set of principal ultrafilters is dense, but has the same cardinality as X, where as the set of ultrafilters has cardinality the power set of the power set of X; hence there should be more ultrafilters than can be gotten than through convergence, in general.Phoenixia1177 (talk) 08:15, 5 September 2012 (UTC)

(This is my last response, I swear) If you're looking for something more concrete using free ultrafilters, let's take X to be the naturals. Put p(k) for the kth prime, A(k) for all numbers divisible by p(k), and B(k) for all numbers congruent 1 mod p(k). Then, for any collection of infinite sets with the finite intersection property there is a free ultrafilter contatining each of them, thus we have free ultrafilters U(n) corresponding to the collection {A(k) : k >= n} union {B(k) : k < n}. Clearly, there is an ultrafilter U for {A(n) : n} in {U(n) : n}'s closure since A(n) is in U(n) for all n, however, there is no sequence in {U(n): n} that converges to it. Since A(k) cannot be in any U(n > k) because A(k) is disjoint B(k), we cannot have A(k) in a tail of any sequence in {U(n) : n}, thus the result:-)Phoenixia1177 (talk) 09:46, 5 September 2012 (UTC)

September 3

Project Euler question

There is a Project Euler problem (whose number I am not quoting so the answer is not given away directly here), where one needs integer solutions to 2b^2 - 2b - n^2 + n = 0. b=3 and n=4 is one solution to this equation. The equations b' = 3b + 2n - 2 and n' = 4b +3n - 3 generate b' and n' which are also solutions to the equation. Two questions please: (1) How do I prove that the b' and n' equations are valid? (2) How does one do Diophantine magic and generate those equations in the first place? -- SGBailey (talk) 08:46, 5 September 2012 (UTC)

The equation is equivalent to 2b(b − 1) = n(n − 1). Now it becomes obvious b = n = 1 is another solution... --CiaPan (talk) 09:22, 5 September 2012 (UTC)

I know the equations work, I've got a dozen solutions and could have a dozen more if I wanted them (they get quite big...). But I'm interested in the proof and creation of the "next set of solutions" equations. Yes 1,1 is a solution. So is 0,1. But so is 3,4. -- SGBailey (talk) 09:36, 5 September 2012 (UTC)

I don't know where they come from, but it's simple enough to show that they work: just plug your formulas for b' and n' into the original equation and simplify. You'll get 2b^2 - 2b - n^2 + n = 0. Under the assumption that you started with a solution, this shows that b' and n' are a solution.--121.73.35.181 (talk) 10:25, 5 September 2012 (UTC)

(1) solved. You are right thanks - when I tried that previously, I went wrong; but it worked ok second time. So (2) where did the generating equations come from??? -- SGBailey (talk) 11:26, 5 September 2012 (UTC)

Convergents (p,q) to the continued fraction expansion of sqrt(2) are (1,1), (3,2), (7,5), (17,12), (41,29) etc (see Pell number). Alternate convergents (1,1), (7,5), (41,29) etc. satisfy

${\displaystyle p^{2}=2q^{2}-1}$

Successive convergents in this sequence are related by the recurrence relations

${\displaystyle p'=4q+3p\quad q'=3q+2p}$

Use the transform

${\displaystyle n={\frac {p+1}{2}}\quad b={\frac {q+1}{2}}}$

and you get the (n,b) sequence (1,1), (4,3), (21, 15) etc. which satisfies

${\displaystyle (2n-1)^{2}=2(2b-1)^{2}-1\Rightarrow 4n^{2}-4n+1=8b^{2}-8b+1\Rightarrow n^{2}-n=2b^{2}-2b}$

with the recurrence relations

${\displaystyle n'=4b+3n-3\quad b'=3b+2n-2}$

Gandalf61 (talk) 12:08, 5 September 2012 (UTC)

Thank you (I think). I didn't understand most of that, but I'll study it for a few days and see if it makes any sense then. -- SGBailey (talk) 13:11, 5 September 2012 (UTC)

Complex variables inequality

Hi. I'm working in a book, and looking at a claim that goes as follows: For ${\displaystyle |e^{z}-1|\leq {\frac {1}{2}}}$, we have ${\displaystyle {\frac {1}{2}}|z|\leq |e^{z}-1|\leq 2|z|}$. I've checked this by doing a change of variables ${\displaystyle \zeta =e^{z}-1}$, parameterizing the circle ${\displaystyle |\zeta |={\frac {1}{2}}}$, and checking that ${\displaystyle {\frac {1}{2}}|\log(\zeta +1)|\leq |\zeta |={\frac {1}{2}}\leq 2|\log(\zeta +1)|}$ all around the circle (for the principal branch). I checked just by graphing the left and right as functions of a real variable, and sure enough, they stayed away from ${\displaystyle {\frac {1}{2}}}$. This is terribly awkward, though. Does anyone know an easier way to see this? Thanks in advance. -GTBacchus 19:54, 5 September 2012 (UTC)

September 6

Implementing an algorithm to generate Proth Primes

Hello all. I'm trying to implement an efficient Proth Prime generator using Proth's theorem, but there are a few concepts that I am a little unclear about. Primarily:

- How many values of 'a' (on a logarithmic scale, perhaps) must be used to make the primality test deterministic?

- How should a given 'a' be chosen? Start at, say, 2 and then simply increment, or what?

- Would it be more efficient to first calculate the Jacobi symbol and test that 'a' is a quadratic nonresidue, or simply select 'a' by some other means?

Apologies for the ignorance, but I'm a computer programmer, not a mathematician! Thanks.

66.87.80.180 (talk) 00:19, 6 September 2012 (UTC)

September 4

September 5

• Pages automatically checked for accidental language links
• Misplaced Pages resources for researchers
• Misplaced Pages help forums