Wikipedia:Reference desk/Archives/Mathematics/2009 November 15

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.

November 15

Equivalence of Vector Norms

Studying for numerics, I came across the problem to show that $||\cdot ||_{1},||\cdot ||_{2},||\cdot ||_{\infty }$ are all equivalent as vector norms on an n dimensional space. I have shown all the other inequalities except $||x||_{1}\leq {\sqrt {n}}||x||_{2}$ for a vector $x\in \mathbb {C} ^{n}$. I have tried all the algebraic "tricks" I know but to no avail. A push in the right direction will be appreciated. Thanks!75.171.178.10 (talk) 00:57, 15 November 2009 (UTC)

What do you mean by "equivalent"? 69.228.171.150 (talk) 03:44, 15 November 2009 (UTC)

Well, if you show that $||\cdot ||_{1},||\cdot ||_{\infty }$ are equivalent and $||\cdot ||_{2},||\cdot ||_{\infty }$ are equivalent, then it follows that $||\cdot ||_{1},||\cdot ||_{2}$ are equivalent. Your definition is that two norms r and s are equivalent if there exist constants a and b such that $ar(x)\leq s(x)\leq br(x)$, right? So, can't you just use the constants from the other two equivalences to get the constants for the third? StatisticsMan (talk) 04:37, 15 November 2009 (UTC)

Here is what I mean. You do not need to show $\|x\|_{1}\leq {\sqrt {n}}\|x\|_{2}$. You just need to show there is some constant such that this inequality is true. But, you said you have already shown the rest. So, you have probably shown $\|x\|_{1}\leq n\|x\|_{\infty }$ and $\|x\|_{\infty }\leq \|x\|_{2}$. Thus, $\|x\|_{1}\leq n\|x\|_{2}$. —Preceding unsigned comment added by StatisticsMan (talk • contribs) 04:45, 15 November 2009 (UTC)

You are right and I should have worded the question carefully. The question is not to just show that they are equivalent (where any constant is okay) but rather to show the inequalities with specific constants. So here is my question. How do I show that $||x||_{1}\leq {\sqrt {n}}||x||_{2}$ for a vector $x\in \mathbb {C} ^{n}$? Thanks!75.171.178.10 (talk) 04:53, 15 November 2009 (UTC)

It's just the Cauchy-Schwarz inequality, that also tells you that ${\sqrt {n}}$ is the best (=smallest) constant. Apply it to the scalar product of (|x₁|,..,|x_n|) and (1,..,1). More generally, notice that $\|x\|_{p}\leq \|x\|_{q}$ always holds true for all x and all 1 ≤ q  ≤ p  ≤ ∞. To get the other inequality with the best constant n ^1/q -1/p use analogously the Hölder inequality. Notice also that all norms in a finite dimensional space are equivalent, so as SM remarks, things are simpler if you do not care about optimality of constants. --pma (talk) 07:11, 15 November 2009 (UTC)

what do you call this matrix?

Resolved

I have a matrix $N=M+M^{T}$ Is there a name for that matrix so I can search for articles on it? I am interested in one that is even more special because M_ij = 0 for all i <= j. I am really interested in properties of N^-1 but would love even just the name of the most general form of N. BTW, I realize N is symmetric, I am looking for information on this particular type of symmetric matrix (which the WP page has nothing on?). PDBailey (talk) 04:13, 15 November 2009 (UTC)

Any symmetric matrix N can be decomposed into M + M^T for some upper triangular matrix M. Let M_ij = N_ij for i > j, M_ij = N_ij/2 for i = j, and M_ij = 0 for i < j. So saying that N is symmetric pretty much sums it up. The fact that you have M with 0 along the diagonal also tells you that the diagonal of N is 0, but I don't know of a special name for that. Rckrone (talk) 04:37, 15 November 2009 (UTC)

Good point, thanks. PDBailey (talk) 11:06, 15 November 2009 (UTC)

Cauchy sequences and continuity

Resolved

How can I show that functions which preserve cauchy sequences between metric spaces are continous? Is the converse true as well? Thanks.-Shahab (talk) 07:17, 15 November 2009 (UTC)

Assume f : X → Y preserves Cauchy sequences. Let x any point in X and (x_j) any sequence converging to x. Consider the sequence (u_j) obtained merging (x_j) with the constant sequence (x), that is, u_2j=x_j and u_2j+1=x for all j in N. The sequence (u_j) still converges to x, so it is a Cauchy sequence, so by assumption f(u_j) is a Cauchy sequence too, and since it is obtained merging f(x_j) with the constant sequence f(x), the sequence (f(u_j)) being Cauchy means that f(x_j) converges to f(x). Therefore f is continuous.

The converse is not quite true whitout additional assumptions. But for instance if f is uniformly continuous, it certainly takes Cauchy sequences into Cauchy sequences. Also, it's of course true if you assume X complete for then a Cauchy sequence on X is convergent, then its image through a continuous f is convergent, hence a Cauchy sequence. On the other hand, if X is not complete, there is a continuous function f : X → R that fails to preserve Cauchy sequences: consider a point ξ on the completion of X but not in X; define a real-valued function on X letting f(x)=1/d(x,ξ) for all x in X, where d is the completion of the distance of X. Then f is continuous on X; there is a Cauchy sequence (x_j) in X converging to ξ; clearly f(x_j) diverges so it's not Cauchy in R. Is all that ok? --pma (talk) 08:26, 15 November 2009 (UTC)

Thanks for the quick and clear response.-Shahab (talk) 08:47, 15 November 2009 (UTC)

An edit conflict arose with pma in my first explanation, and afterwards, when trying to reinsert my explanation, an edit conflict arose with Shahab! I will include my post here anyway (although I see that Shahab is content with pma's explanation). Here is an explanation that functions which preserve limits of convergent sequences must be continuous (note that, below I am proving another point which is used in the first paragraph of pma's proof above):

Suppose f has the above property. To show that f is continuous, we must show that f is continuous at every point in its domain (refer to this metric space as X). Suppose x is in X. Let $U_{n}$ be an open ball containing x of radius ${\frac {1}{n}}$, for each $n\in \mathbb {N}$. Note that this is a descending chain of open sets $U_{1}\,\supseteq \,U_{2}\,\supseteq \,U_{3}\,\supseteq \,\cdots$. Suppose V is an open set containing $f(x)$ - then $x\in f^{-1}(V)$. For each n, let $x_{n}\in U_{n}\setminus f^{-1}(V)$. If x is not an interior point of $f^{-1}(V)$, $x_{n}$ exists for all $n\in \mathbb {N}$. Prove that $({x_{n}})_{n\in \mathbb {N} }$ converges to x, but that the image of this sequence under f does not converge to $f(x)$. We arrive at a contradiction in assuming that x was not an interior point of $f^{-1}(V)$; therefore, f is indeed continuous as desired.

See also the article Cauchy-continuous function (but try to explore this notion in greater depth before doing so).

A counterexample to the converse is the function $f:(0,1)\to \mathbb {R}$ defined by $f(x)={\frac {1}{x}}$. However, do you think that the extra hypothesis that f be uniformly continuous ensures the truth of the converse? Hope this helps. --PST 08:51, 15 November 2009 (UTC)

Thank you PST. As you said, I was content with pma's explanation but your post was insightful.-Shahab (talk) 10:03, 15 November 2009 (UTC)

Yes, that is what I was also thinking: "f uniformly continuous" also makes the converse true. I'm not sure if you meant to suggest it as a further exercise for Shahab, so I'll hide the answer below as I learned from you, not to spoil the exercise ;-)

(Click the "show" button to see the answer or the "hide" button to hide it.)

If f is uniformly continuous with modulus of continuity ω, and if (x_j) is a Cauchy sequence in X, then f(x_j) is a Cauchy sequence in Y, because d_Y(f(x_p), f(x_q))  ≤ ω(d_X(x_p, x_q)) for all p and q.

Proving formula for Riemann-Zeta function, k even

Resolved

Hey, I'm trying to work through the proof of the formula for the Riemann-Zeta function for even k, which involves the Bernoulli numbers, in Koblitz's book on elliptic curves and modular forms and I am stuck. I believe I am fine up to

$\pi ia+{\frac {2\pi ia}{e^{2\pi ia}-1}}=1+\sum _{n=1}^{\infty }{\frac {a}{a+n}}+{\frac {a}{a-n}}$.

The book then says to let $x=2\pi ia$ so I assume I get rid of all a's by using $a={\frac {x}{2\pi i}}$. This gives

${\frac {x}{2}}+{\frac {x}{e^{x}-1}}=1+\sum _{n=1}^{\infty }{\frac {\frac {x}{2\pi i}}{{\frac {x}{2\pi i}}+n}}+{\frac {\frac {x}{2\pi i}}{{\frac {x}{2\pi i}}-n}}$

I then substitute the formula $\sum _{k=0}B_{k}{\frac {x^{k}}{k!}}={\frac {x}{e^{x}-1}}$ and subtract the ${\frac {x}{2}}$ to the other side. I also thought it might be simpler to multiply through by $2\pi i/2\pi i$ in the sum. So, I do this and get

$\sum _{k=0}^{\infty }B_{k}{\frac {x^{k}}{k!}}=1-{\frac {x}{2}}+\sum _{n=1}^{\infty }{\frac {x}{x+2\pi in}}+{\frac {x}{x-2\pi in}}$.

Now, I'm not sure what to do. Koblitz basically says we're done here. I thought about doing a power series for both terms. So, we have

${\frac {x}{x+2\pi in}}={\frac {\frac {x}{2\pi in}}{1-(-{\frac {x}{2\pi in}})}}=\sum _{m=0}^{\infty }(-1)^{m}\left({\frac {x}{2\pi in}}\right)^{m+1}$

${\frac {x}{x-2\pi in}}={\frac {-{\frac {x}{2\pi in}}}{1-{\frac {x}{2\pi in}}}}=-\sum _{m=0}^{\infty }\left({\frac {x}{2\pi in}}\right)^{m+1}$

Putting everything together gives

$\sum _{k=0}^{\infty }B_{k}{\frac {x^{k}}{k!}}=1-{\frac {x}{2}}+\sum _{n=1}^{\infty }\sum _{m=1}^{\infty }[(-1)^{m}-1]\left({\frac {x}{2\pi in}}\right)^{m}$.

Now, the problem is, I am supposed to compare powers to get the formula. I compare second powers of x and I get

${\frac {B_{2}}{2}}=\sum _{n=1}^{\infty }-2{\frac {1}{(2\pi in)^{2}}}$.

This is not a sum of the form of the Riemann-Zeta function. Do any of you see what I am doing wrong? Perhaps using the power series was not the right idea? Thanks. StatisticsMan (talk) 17:44, 15 November 2009 (UTC)

if you kick your last sum a bit you get $B_{2}\pi ^{2}=\sum 1/n^{2}=\zeta (2)$. Isn't this the formula you wanted? It's not clear to me what you're looking for here... Tinfoilcat (talk) 18:31, 15 November 2009 (UTC)

Yea. I was just not thinking straight. Thanks. StatisticsMan (talk) 21:25, 15 November 2009 (UTC)

(combinatorial) description of 126 points and 56 symplecta of E7 polytope (gosset polytope)

Hello,

as hinted at in the column on the right of Gosset_1_32_polytope, that polytope has 126 6-cells of one type (corresponding with the leftmost node in the Coxeter-Dynkin diagram given there) and 56 6-cells of another type ((corresponding with the rightmost node in the Coxeter-Dynkin diagram given there). I am almost exclusively interested in a combinatorial model (so the angles and distances don't really matter to me)

I would like to understand both types. I already found this description of the 126 on the left: they are the 56 vectors of length 8 with 6 zero entries, one +1 and one -1, and the 70 vectors of length 8 with 4 entries equal to 1/2, and 4 equal to -1/2.

(Note that the inner products between two of them can be -2,-1,0,1,2)

Is a similar thing possible for the 56 other 6-cells (allowing me to see which are incident?)

In order to clarify my question, F4_polytope#Constructions already answers this question for the 24-cell:

24 vertices:

8 vertices obtained by permuting

(±1, 0, 0, 0)

and 16 vertices of the form

(±½, ±½, ±½, ±½).

The vertices of the dual 24-cell are given by all permutations of

(±1, ±1, 0, 0).

Many thanks,81.82.86.83 (talk) 20:24, 15 November 2009 (UTC)

Free Burnside group B(2,4)

I want a permutation representation of the generators of the free Burnside group B(2,4). --84.61.166.115 (talk) 21:04, 15 November 2009 (UTC)

The article Burnside group should answer your question (particularly a section towards the botton of the article). I think that this is merely a matter of looking at the appropriate definition. Hope this helps. --PST 04:12, 16 November 2009 (UTC)

Why is the free Burnside group B(2,4) not a subgroup of the symmetric group S₁₅? --84.61.166.115 (talk) 07:53, 16 November 2009 (UTC)

The smallest transitive permutation representation is on 256 points, and it has intransitive permutation representations on 64+8=72 and 16+16+8=40 points. B(2,4) is not contained in S15 because B(2,4) has order 4096 and the Sylow 2-subgroup of S15 (which has exponent 8 anyways) has order 2048. Alternatively, B(2,4) has nilpotency class 5, while the Sylow 2-subgroup of S15 has nilpotency class 4. In general, p-groups are not contained in particularly small symmetric groups. JackSchmidt (talk) 12:36, 16 November 2009 (UTC)

Is your last remark just a general principle, or is there a theorem along those lines? Algebraist 13:06, 16 November 2009 (UTC)

I'm not sure I understand the question. It is a general principle because there are many theorems along those lines. There are many ways to quantify groups and subgroups, and in most of those ways, the subgroups of symmetric groups tend to be more boring than "expected". JackSchmidt (talk) 14:42, 16 November 2009 (UTC)

I'm not sure I understand the question either, but I certainly understand the answer. Thanks. Algebraist 20:40, 16 November 2009 (UTC)

For what it is worth, I think 16+16+8=40 is the minimum degree of a faithful perm rep. One of the degrees has to be 16, since the Sylow S8 has too low of nilpotency class. WLOG all of the degrees are at least 8, since every subgroup of index at most 4 contains the center, and so contributes nothing to removing the kernel. An exhaustive check of triples then showed 16,16,8 to be the least degree of a faithful triple (quadruples would have to be 16+8+8+8=40 too, so no improvement). JackSchmidt (talk) 21:31, 16 November 2009 (UTC)

Please post a permutation representation of the generators of the free Burnside group B(2,4) here! --84.61.166.115 (talk) 19:09, 16 November 2009 (UTC)

I'm not sure how useful it is, but here are the generators of B(2,4) under a faithful permutation representation on 16+16+8=40 points:

(1,3,5,7)(2,16,10,9)(4,11)(6,15,13,12)(8,14)(17,19)(18,32)(20,27,24,30)(21,23)(22,31)(25,29,28,26)(33,34)(35,38,37,40)(36,39), and

(1,2)(3,9,7,12)(4,13,8,10)(5,6)(11,15)(14,16)(17,18,21,22)(19,25,30,31)(20,26)(23,28,27,32)(24,29)(33,36)(34,40,39,38)(35,37).

They can be generated in the GAP computer algebra system with the following 3 minute script

LoadPackage("anupq");; g:=Pq(FreeGroup(2):Prime:=2,Exponent:=4); subs:=List(ConjugacyClassesSubgroups(g),Representative);; repeat h1:=Random(Filtered(subs,h->Index(g,h)=16)); h2:=Random(Filtered(subs,h->Index(g,h)=16)); h3:=Random(Filtered(subs,h->Index(g,h)=8)); until 1=Size(Intersection(Core(g,h1),Core(g,h2),Core(g,h3))); i1:=FactorCosetAction(g,h1);; i2:=FactorCosetAction(g,h2);; i3:=FactorCosetAction(g,h3);; g0:=DirectProduct( Range(i1), Range(i2), Range(i3));; rep:=GroupHomomorphismByImages( g, g0, GeneratorsOfGroup(g), List(GeneratorsOfGroup(g), x -> Image( Embedding(g0,1), Image(i1,x)) * Image( Embedding(g0,2), Image(i2,x)) * Image( Embedding(g0,3), Image(i3,x)) ));; SmallGeneratingSet(Image(rep));

You can use similar ideas to construct other permutation representations. JackSchmidt (talk) 19:52, 16 November 2009 (UTC)

I want a permutation representation of the generators of the free Burnside group B(2,3). --84.61.166.115 (talk) 19:36, 16 November 2009 (UTC)

I want a permutation representation of the generators of the free Burnside group B(3,3). --84.61.166.115 (talk) 19:36, 16 November 2009 (UTC)

Why is the free Burnside group B(2,3) not a subgroup of the symmetric group S₈? --84.61.166.115 (talk) 19:36, 16 November 2009 (UTC)

This is not the sort of question you should ask in public. This is the sort of question you should be able to answer immediately in your head. JackSchmidt (talk) 20:01, 16 November 2009 (UTC)

Why is the free Burnside group B(3,3) not a subgroup of the symmetric group S₁₇? --84.61.166.115 (talk) 19:36, 16 November 2009 (UTC)

You should probably look at the formula for the order B(n,3) and compare it to the order of the Sylow 3-subgroup of S17. JackSchmidt (talk) 20:01, 16 November 2009 (UTC)

Which one of these is wrong?

Resolved

I have little formal training in computer science, so forgive me for my ignorance. I was looking through some articles on complexity classes, and I noticed this on the TFNP page:

TFNP = FP would imply P = NP $\cap$ coNP, and therefore that factoring and simplex pivoting are in P.

TFNP ≠ FP would imply NP = coNP.

So either factoring is in P, or NP = co-NP. Unless all the computer scientists in the world are wrong, one or both of the statements in the article are incorrect. This was also mentioned by an IP on the talk page. I'd like to know what reality is so that the article can be fixed. « Aaron Rotenberg « Talk « 22:49, 15 November 2009 (UTC)

I think the article may be wrong in stating that ${\rm {FP\subseteq TNFP}}$ is known. It might be that ${\rm {FP\subsetneq TNFP}}$ implies P=coNP, but FP may be bigger than TNFP. It's well known though that factoring is in NP $\cap$ coNP. The complexity zoo is a good reference for these obscure classes. 69.228.171.150 (talk) 03:15, 16 November 2009 (UTC)

The inclusion ${\rm {FP\subseteq TNFP}}$ is a trivial consequence of the definitions. That TFNP = FP would imply P = NP $\cap$ coNP is also easy to see, as the characteristic function of any language in NP $\cap$ coNP is in TFNP. The claim that TFNP ≠ FP implies NP = coNP is almost certainly wrong (of course I can't prove that as we do not even know that NP ≠ P, let alone TFNP ≠ FP). — Emil J. 13:04, 16 November 2009 (UTC)

Thanks for fixing the article. « Aaron Rotenberg « Talk « 22:30, 16 November 2009 (UTC)