User arupinski - MathOverflow

Answer by ARupinski for Signless Stirling Numbers of 1st Kind and Probabilistic Descent

2013-06-13T01:55:26Z

Start with an arbitrary permutation in $S_n$ written in cycle form:

\begin{align*} \psi := (\pi(n-1),\ldots,\pi(n_1))(\pi(n_1-1),\ldots,\pi(n_2))&\ldots(\pi(n_{k-1}-1),\ldots,\pi(n_k)) \end{align*}

Next, for $\ell = 1\ldots k$, define the sets $N_\ell$ as the collections of elements in each cycle of this permutation: \[ N_\ell := \{\pi(n_{\ell-1}-1),\ldots,\pi(n_\ell)\} \]

Now impose the following condition on the $N_\ell$:

\[ \max\left(\nu|\nu\notin\bigcup_{i<\ell}N_i\right)\in N_\ell \]

Clearly for a given permutation in cycle notation, this inclusion condition defines a unique order on the cycles (the leftmost cycle is the cycle containing the maximal element and from there one chooses the cycle with the largest remaining element to be the next cycle, and so forth). Then, given the ordered cycles one obtains a unique descent associated to $\psi$ by taking the lengths of each cycle to be the step sizes starting at $n$, so if \psi satisfies the max element condition on its ordered cycles, we associate it to the descent $[n=n_0,n_1,\ldots,n_k=0]$.

Finally, one notes that the count of permutations whose cycle structure leads to a given descent is exactly the numerator of the probability for the original descent; since every permutation leads to some descent by this process, one gets the bijection you sought.

Another way to view the above bijection is that when you choose your first number, make a cycle of length represented by the difference of the number you chose from the start number, place the number $n$ at the start of your cycle and fill the remaining slots of the cycle however you like. Then choose your next descent step at random, form another cycle whose length is the difference between this step and the previous one, place the largest number not yet used at the start of the cycle, and fill the remainder any way you like with the unused numbers. Repeat until you exhaust your descent; at this point every number will have been put into some cycle and you will have a permutation corresponding to your particular descent.

Picturing a Certain Torus and Klein Bottle

2013-05-15T02:01:59Z

The other day I was explaining orientability to someone and we were walking through some of the statements about orientability on the Wikipedia page on the topic. While I was able to satisfy his curiosity, one statement on that page (which I did not even attempt to delve into with him) has been nagging me since then:

"For example, a torus in $K^2\times S^1$ can be one-sided and a Klein bottle in the same space can be two-sided."

Because this statement bothered me (since it runs counter to normal intuition about orientable surfaces in Euclidean spaces), I have been thinking about it more over the last few days. I have been able to determine which copies of these submanifolds should have the stated properties and convince myself how the non-orientability of the ambient space $K^2\times S^1$ allows for the submanifolds in question to twist back on themselves in unusual ways, but nevertheless I still cannot form a decent picture of what this really means.

The real issue with my understanding what is going on with these submanifolds seems to be that although these phenomenon occur in a non-orientable space, this space can itself be embedded in an orientable space and so it seems that these odd tori and Klein bottles should therefore embed in an orientable space as well and so I should have some chance of visualizing these phenomena when I project down to $\mathbb{R}^2$ or $\mathbb{R}^3$

Question: Does anyone have a good picture or other approach to help visualize what a one-sided torus or two-sided Klein bottle looks like?

So while it may be too much to hope for a projection that accurately reflects the sidedness of these creatures, I am hoping someone may have a decent projection of either of these creatures to the plane or 3-space that shows some manifestations of their odd behaviour in their ambient space. Or, barring an actual picture, perhaps someone who has thought about this more has some other way of thinking about them which at least gives a better intuitive sense of how to look at them in their ambient space and 'see' (whatever that may mean when you think about them) these counterintuitive features.

Does this Linear Algebra Construction have a Name?

2013-05-06T23:15:17Z

Let $\mathcal{R}$ be a ring and let $v^0,\ldots,v^{k-1}\in\mathcal{R}^m$ with $m \geq k$. Suppose we wish to find $w\in Span(v^0,\ldots,v^{k-1})$ such that $k-1$ specified coordinates of $w$ vanish (say $w[j_0] = \ldots = w_[j_{k-2}] = 0$). Then the following determinantal construction for $w$ does the trick:

$w = \sum_{i=1}^k (-1)^k\cdot\det\begin{pmatrix}{v^0}[j_0]&{v^0}[j_1]&\ldots&{v^0}[j_{k-2}]\\{v^1}[j_0]&{v^1}[j_1]&\ldots&{v^1}[j_{k-2}]\\\vdots&\vdots&\ddots&\vdots\\\widehat{v^i[j_0]}&\widehat{v^i[j_1]}&\ldots&\widehat{v^i[j_{k-2}]}\\\vdots&\vdots&\ddots&\vdots\\{v^k}[j_0]&{v^k}[j_1]&\ldots&{v^k}[j_{k-2}]\end{pmatrix}\cdot v^i$

The individual coordinates of $w$ also have a nice determinantal form (which follows from the above expression):

$w[i] = \det\begin{pmatrix}v^0[i]&v^0[j_0]&v^0[j_1]&\ldots&v^0[j_{k-2}]\\v^1[i]&v^1[j_0]&v^1[j_1]&\ldots&v^1[j_{k-2}]\\\vdots&\vdots&\vdots&\ddots&\vdots\\v^{k-1}[i]&v^{k-1}[j_0]&v^{k-1}[j_1]&\ldots&v^{k-1}[j_{k-2}]\end{pmatrix}$

For example, suppose we start with the 3 vectors $v^0 = \langle 2,3,5,7,11,13\rangle$, $v^1 = \langle17,19,23,29,31,37\rangle$ and $v^2 = \langle 41,43,47,53,59,61\rangle$ and wish to find a vector $w$ in their span whose final 2 coordinates are 0. Then the above formulas give us the following vector:

\begin{align*} w &= \det\begin{pmatrix}31&37\\59&61\end{pmatrix}\cdot v^0 - \det\begin{pmatrix}11&13\\59&61\end{pmatrix}\cdot v^1 + \det\begin{pmatrix}11&13\\31&37\end{pmatrix}\cdot v^2\\ &= -292\cdot v^0 + 96\cdot v^1 + 4\cdot v^2\\ &= \left\langle\det\begin{pmatrix}2&11&13\\17&31&37\\41&59&61\end{pmatrix},\det\begin{pmatrix}3&11&13\\19&31&37\\43&59&61\end{pmatrix},\det\begin{pmatrix}5&11&13\\23&31&37\\47&59&61\end{pmatrix},\right.\\ &\;\;\;\;\;\;\;\;\;\;\left.\det\begin{pmatrix}7&11&13\\29&31&37\\53&59&61\end{pmatrix},\det\begin{pmatrix}11&11&13\\31&31&37\\59&59&61\end{pmatrix},\det\begin{pmatrix}13&11&13\\37&31&37\\61&59&61\end{pmatrix}\right\rangle\\ &= \langle 1212, 1120, 936, 952, 0, 0\rangle \end{align*}

These formulas are easily derived/proved using Cramer's rule and/or other methods involving exterior products (which is how I came up with them when I was trying to construct such a vector), and like Cramer's Rule are rather beautiful, so I would be surprised if they are not already written down/used somewhere. Nevertheless, I don't recall having ever seen such constructions in any Linear Algebra books.

Main Question: Has anyone seen either of the above equivalent formulas before? If so, do they have a name?

Secondary Question: Whether or not they have a name, has anyone seen these formulas used as part of any other proofs?

Update: After thinking more about Question 2 over the last few days I realized this sort of construction $could$ arise in some group representation problems where one wants to explicitly find a character which is zero on certain conjugacy classes, such as when one is calculating induced representations. But I have definitely never seen it in any such character-theoretic arguments, and it is not even immediately clear to me whether it would necessarily give non-virtual representations in general. On the other hand, studying for a given group $G$ which sets of characters paired with which sets of conjugacy classes give rise to pure representations via this construction (aside from the trivial cases of pairs obtained from induction of representations) sounds intriguing enough that I will probably take a look at it. Still not clear if the construction has actually been used in any such proofs elsewhere though...

Answer by ARupinski for $n$-in-a-row game on $\mathbb{R}^2$

2013-05-02T04:12:34Z

So now Im thinking about the following approach. Let $H$ be the discrete hypercube $[1,...,kn]^d$ with $k,d>> n$ (im not sure how big I need them yet, it just seems that I need them to be sufficiently large compared to $n$ for this to work). I can project $H$ onto $\mathbb{R}^2$ via a linear transformation which sends the unit basis vectors of $\mathbb{R}^d$ to $\mathbb{Q}$-linearly independent vectors in $\mathbb{R}^2$. The point of this is that the only straight lines of points in the projection come from straight lines in $H$. Now P1 plays all his moves on these projected points and I want to argue that the total number of lines of $n$ points in a row contained in $H$ is orders of magnitude greater than the number of lines P2 could have blocked (even accounting for the fact that if P2 played on grid points it would block several potential $n$-in-a-rows simultaneously). The approach then boils down to a slightly stronger version of Van der Waerden's theorem for a bichromatic coloring of $H$. I just cannot figure out the estimates necessary to show for sure that once all of $H$ has been colored (with only the assumption that P1 only colors points of $H$ on each of his plays) there must be enough monochromatic $n$-in-a-rows for sufficiently large $d,k$ that P2 could not possibly have blocked them all. (I assume $k>>n$ to give the possibility of $n$-in-a-rows running at slanted angles through $H$ so that P2 cannot simply block by playing on lines parallel to the coordinate axes). Anyone have ideas on how to rigorously complete this argument or see any fatal flaws I overlooked?

Answer by ARupinski for Edge-coloring of the complete graph without any rainbow paths

2013-01-29T04:07:59Z

It seems that one can use a similar trick to that used in your construction on $K_{2^k}$ for any $K_{4n}$: label the vertices by elements of $G = (\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2n\mathbb{Z})$ and assign edge colors by ~~the difference of the two endpoints~~ (EDIT: as noted in Ilhee's comment, this won't be well-defined; am thinking about possible modifications). Since the sum of all the elements of $G$ is the identity, the same argument which shows your coloring of $K_{2^k}$ is rainbow-free applies to this coloring of $K_{4n}$.

Unfortunately this argument fails when we try to use it to label $K_{4n+2}$ by elements of $(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/(2n+1)\mathbb{Z})$ since the sum of the elements of the group is not the identity in this case.

My gut tells me there is some clever way to label the vertices in the $K_{4n+2}$ so as to define colors on the edges which force your condition, but I don't see it; I'll have to think about it some more.

Answer by ARupinski for Automorphism of finite groups and Hurwitz spaces

2013-01-20T00:25:12Z

Such automorphisms need not extend to inner automorphisms of $S_n$. Take the dihedral group $D_8$ sitting transitively inside $S_4$, say as the following set of permutations: $\{(1)(2)(3)(4), (13)(2)(4), (1)(3)(24), (12)(34), (14)(23), (1234), (13)(24), (1432)\}$. Now the sets of reflections $\{(13)(2)(4), (1)(3)(24)\}$ and $\{(12)(34),(14)(23)\}$ are equivalent to one another via an outer automorphism of $D_8$, but clearly this automorphism is not inner in $S_4$.

Does this poset have a unique minimal element?

2012-12-24T16:35:44Z

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees (with at least one edge to exclude the trivial cases pointed out by Joel) and the poset relation $\leq$ is defined by $T \leq U$ if $T$ can be obtained from $U$ by successively deleting one leaf node at a time in such a way that each intermediate tree is also an element of $\mathcal{AFT}$.

The smallest element of $\mathcal{AFT}$ is the seven node tree which is the Dynkin diagram of $E_7$ (and which I will therefore refer to simply as $E_7$ from herein):

So $E_7$ is certainly a minimal element in the above partial order.

Question: Does $(\mathcal{AFT},\leq)$ have a unique minimal element, namely $E_7$?

There are several equivalent formulations of this question which I have considered, hoping one of them might lead somewhere useful:

Question 2: Can every element of $\mathcal{AFT}$ be obtained by starting at $E_7$ and successively adjoining leaf nodes so that we remain in $\mathcal{AFT}$ at every stage?

Question 3: Is there an element of $\mathcal{AFT}$ besides $E_7$ such that deleting $any$ single leaf node results in a tree not in $\mathcal{AFT}$.

Question 3 in particular seems simple enough that it must have been answered somewhere before, but alas almost any search for 'automorphism-free' and 'trees' results in papers about the result that almost every tree has an automorphism or results on the fixed vertices/edges of trees under automorphisms.

Trying to construct a minimal example larger than $E_7$ for Question 3 keeps leading to near-misses where all but one leaf nodes' removal takes us outside $\mathcal{AFT}$, but after removing this one leaf node, there is still a sequence of removals remaining in $\mathcal{AFT}$ that leads back to $E_7$ which is the best evidence I have so far that Question 1 is true.

So, does anyone know where this might have been considered already, and if so, if the answer to Question 1 is affirmative?

Answer by ARupinski for Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

2012-11-07T04:06:04Z

It's possible I messed up in my calculations, so by all means check it to be sure, but I think the following is an example of what you seek:

Start with a copy of $K_{5,103}$ with vertices $v_1\ldots v_5,w_1\ldots w_{103}$ and remove the edges $v_iw_i$ for $1\leq i\leq 5$. Add two copies of $K_2$ to make a total of 512 edges. Then unless I messed up somewhere in my calculation, no induced subgraph can have exactly 256 edges in it.

There were another of other near misses I found (similar initial setups which had exactly 1 way (up to relabelling of vertices) to remove vertices leaving exactly 256 edges), so it shouldn't be hard to modify this construction to find an example if it turns out the above example fails after all.

Answer by ARupinski for A simple question about the center of a finite group

2012-10-25T02:57:35Z

As it is not entirely clear where the containments are meant to be, I will assume you are asking about the case $N\triangleleft K\triangleleft G$; in this case $Z(G) = Z(G/N) = 1$ is not sufficient in general to guarantee $Z(G/K)$ is also trivial. As an example, take $N$ to be the Klein-4 subgroup of $S_4$ and $K = A_4$. Then $G/N\cong S_3$ so $Z(G) = Z(G/N)$ is trivial, but $G/K$ is abelian (isomorphic to $\mathbb{Z}/2\mathbb{Z}$) and so $Z(G/K)$ is not trivial.

Answer by ARupinski for Getting a bound on the coefficients of the factor polynomial

2012-10-03T21:50:54Z

Any such bound will depend only on $n$ and $m$ since once can take for instance $f(x) = x^n-1$ (so $M = 1$). Then depending on $n$, the cyclotomic factor $\Phi_n(x)$ has coefficients as large as you like: for example $\Phi_{105}(x)$ has coefficients of modulus $2$, $\Phi_{385}(x)$ has coefficients of modulus $3$, for further references see OEIS sequence A013594 (http://oeis.org/A013594).

Answer by ARupinski for Subwords of cube-free binary words

2012-09-20T03:17:44Z

Try this: start with the infinite Thue-Morse word $TM = 0110100110010110...$ which is known to be cubefree and make the following transformations:

$0 \Rightarrow x0$

$1 \Rightarrow x1$

This gives the the infinite word:

$TM^\prime = x0x1x1x0x1x0x0x1x1x0x0x1x0x1x1x0x...$

Next make the following transformation on $TM^\prime$:

$x\Rightarrow 11$

$0\Rightarrow 0$

$1\Rightarrow 00$

This gives the following infinite word:

$C = 110110011001101100110110110011...$

Clearly $C$ does not contain the subword $010$, and unless I overlooked something in my analysis, the cube-freeness of $TM$ implies $C$ is also cube-free, which would mean there is no upper bound to the size of cube-free binary strings not containing all six of the given strings.

(Incidentally, the composition of these two transformations is equivalent to performing the transformation $0\Rightarrow 110$, $1\Rightarrow 1100$ on $TM$ to get $C$, but I figured the intermediate step makes it a bit clearer, to me at least, why $C$ should be cube-free).

If anyone sees any flaw in the reasoning that $C$ is cube-free, please do point it out.

Answer by ARupinski for Induction from cyclic / Sylow subgroup are there any nice properties ?

2012-08-18T02:02:13Z

This is a set of observations that should help you understand your inductions of non-trivial characters. If I read Marty's answer correctly, this should be a concrete way of understanding what he is saying using your particular example.

First note that each non-trivial character $\chi$ has a conjugate character $\overline{\chi}$ and that the inductions of $\chi$ and $\overline{\chi}$ must also be conjugate. Next, irreducible characters occur in sets which are related to one another by outer automorphisms of the dual group, these sets are defined by those irreducible characters with common kernel. Finally, note that the induction of the regular representation of the subgroup is the regular representation of the big group.

How does this help? Well in your example, lets look at what remains from the regular representation of $GL_3(\mathbb{F}_2)$ after we take away the induction of the trivial character of the Sylow 7-group. The remaining pieces are:

$3V_{3a} \oplus 3V_{3b} \oplus 6V_6 \oplus 6V_7 \oplus 6V_8$

Each induction of the 6 nontrivial characters must have dimension 24, and since the nontrivial characters are all more or less equivalent (up to outer automorphisms of the dual group to be technical), all their inductions should look more or less the same as well. This means that each induces to either $W = V_{3a}\oplus V_6 \oplus V_7\oplus V_8$ or its conjugate $\overline{W} = V_{3b}\oplus V_6 \oplus V_7\oplus V_8$.

With a bit of extra work, you would then find that if a character $\chi$ of the Sylow 7-subgroup induces to $W$ then so do the characters of $\chi^{\otimes 2}$ and $\chi^{\otimes 4}$ while the characters of $\chi^{\otimes 3}$, $\chi^{\otimes 5}$, and $\chi^{\otimes 6}$ will induce to $\overline{W}$, although the particular split on the exponents don't matter to your particular question (as currently stated).

Failure of a basic fact from Representation Theory

2012-08-06T23:19:43Z

Recently I have been working with a certain subgroup of $GL_{10}(\mathbb{F}_2)$ and for various reasons was fairly sure it contained a normal subgroup isomorphic to $A_5$. Today I was able to affirmatively show that this presumed copy of $A_5$ does indeed exist in the bigger group. Now the matrices composing this copy of $A_5$ are themselves $2\times 2$ matrices over a certain commutative 5-dimensional algebra $\mathcal{S}$ (necessarily with zero divisors) over $\mathbb{F}_2$; this gives rise to a 2-dimensional representation of $A_5$ over $\mathcal{S}$ which I am fairly sure is irreducible (as opposed to just indecomposeable).

Now it is a fairly standard exercise early in learning representation theory to show that a simple group cannot have an irreducible representation of dimension 2. As the proof of this simple fact relies only on considerations involving the characters of elements of order 2, does the existence of the above representation rely only on the fact that I am working in characteristic 2, or is it related to the fact that I am working with rings with zero divisors as opposed to an algebraically closed field, or something else more subtle? I am primarily curious as to whether it is solely related to the characteristic, as I am also working with some related groups defined over commutative rings in other characteristics which I suspect also contain subgroups isomorphic to $A_5$. Hopefully someone with more background in modular representation theory than I can shed some helpful light on this situation.

Answer by ARupinski for Minimal blocking objects with shadows like a cube

2012-08-04T02:14:26Z

For $C_3(n)$ an absolute upper bound is $3(n-1)^2+3$ which can always be attained by taking the cubes on three faces adjacent to a given corner, removing the corner itself, and removing all but one cube on each edge incident to the corner. Unfortunately, this gives a bound of 15 in the $n=3$ case., so does not improve your particular case. Somewhat generalizing this construction to higher dimensions, for $d\geq 4$ one gets an absolute upper bound for $C_d(n)$ of

$[n^d-(n-1)^d]-d(n-1)+1$

To prove this always works, consider $C_d(n)$. We will replace each cube by its center point and consider the lattice as in Joseph's previous question which he references.

WLOG, let one corner of $C_d(n)$ be centered at the origin. The lines we want to block have $(d-1)$ coordinates fixed and one coordinate which varies. Now consider the set of all cubes whose center has at least one coordinate equal to 0; this is exactly the set of all cubes lying on one (or more) $(d-1)$-dimensional faces adjacent to our origin cube. There are $[n^d - (n-1)^d]$ such cubes. Now remove all cubes along the edges incident to our cube centered at the origin, this removes $d(n-1)+1$ cubes leaving the set $S_d(n)$ which consists of all cubes with at least one and at most $(d-2)$ coordinates equal to 0. The only lines which do not intersect this set are those which have $(d-1)$ fixed coordinates equal to 0, i.e. the lines incident to our cube centered at the origin. Since cubes are adjacent iff they differ in exactly one coordinate, it is easy to check that the $S_d(n)$ is connected for $d\geq 4$ but not connected for $d=3$. So we need only add our cube centered at the origin, and one cube adjacent to it to block the remaining lines while ensuring the entire collection is connected.

Note that if the above held for $d=3$, one could use it to push our bound down from Joseph's 15 to 14; however the set $S_3(n)$ consists of 3 disconnected pieces and so the reasoning leading to this formula fails. However this formula does imply that as $d$ or $n$ gets large, one can block all lines with an arbitrarily small fraction of all available cubes.

There is probably a way to do some more inclusion-exclusion to further eliminate some particular pieces of $S_d(n)$ as unnecessary for blocking purposes and thereby further reduce our bound, but offhand I don't see it.

Answer by ARupinski for Lattice-cube minimal blocking sets

2012-08-01T23:26:32Z

This is somewhat of an expanded comment on Eoin's answer and his follow-up question of whether such sets correspond to hyperplanes in the discrete torus.

In the $C_2(n)$ case minimal blocking sets correspond to permutation of ${1...n}$ (consider a permutation matrix; then a minimal blocking set can be formed by choosing the points corresponding to the positions of the 1's in this matrix). Conversely, every minimal blocking set in the $d=2$ case arises this way, so for $n\geq 4$ not every blocking set corresponds to a hyperplane on a torus.

In the $d=3$ case this can be extended to see that every minimal blocking set corresponds to a set of $n$ permutations whose permutation matrix sums to the all 1's matrix (think of stacking the permutation matrices up to form our cube); again it is clear that not all such sets can correspond to hyperplanes if $n \geq 4$.

For $d \geq 4$, one can apply an analogous stacking approach using sets in $C_{d-1}$ to generate all minimal blocking sets although it is not immediately obvious to me how to relate these sets to permutations easily.

For $n = 2$, it is easy to see that there are exactly two minimal blocking sets in any dimension and both always correspond to toric hyperplanes, and it seems that all minimal blocking sets are also toric hyperplanes for $n=3$ in any dimension due to how little room there is in $S_3$ to form such sets (this should follow from induction on the dimension; once one lays down the first $d-1$-dimensional layer and one point in the next layer, this should determine where all the remaining points must go in the last two layers). If anyone can easily formalize this idea for the $n=3$ case (or provide a counterexample) I would love to see it.

Does this knot invariant distinguish trefoil chiralities?

2012-04-30T12:59:34Z

Let $C_N$ denote the labelled configuration of $N^{th}$ roots of unity with $p_J = e^{\frac{2\pi iJ}{N}}$ for $J = 1\ldots N$.

As a corollary of something else I was playing around with, I recently proved the following:

Theorem: Every tame knot (or link) $K$ has a (not necessarily minimal) stick presentation which such that the sticks can be projected onto the set of chords of some $C_N$ with the following crossing condition: Whenever the projection has chords $p_{J_1}p_{J_3}$ and $p_{J_2}p_{J_4}$ such that $1\leq J_1 < J_2 < J_3 < J_4\leq N$ then $p_{J_1}p_{J_3}$ crosses in front of $p_{J_2}p_{J_4}$. (In other words for any two intersecting chords in the projection, the chord which has the lowest numbered endpoint passes in front of the other chord).

Germane to this question is the fact that the theorem leads to a knot invariant which, for lack of a better name, I will call the circular stick number of $K$ and which is defined to be the minimum $N$ needed to obtain a projection of $K$ with the above properties.

My proof of the above theorem was very non-constructive, so I wanted to see some concrete realizations of such projections. And after some work, I was able to find that for the left trefoil knot, the circular stick number is 7. After much more playing around on $C_7$ and not finding a projection of the right trefoil, I moved on to $C_8$ where I was able to find a projection of the right trefoil.

Main Question: Does this invariant actually distinguish chiralities of the trefoil, or can someone find a projection of the right trefoil with the above properties on $C_7$? If it doesn't distinguish chiralities in this case, is it possible it distinguishes chiralities of some other pair of knots, or does anyone see a slick way to see that it cannot distinguish chiralities?

Secondary Question: (Mainly for knot theorists, or anyone with a deeper knowledge of knots than I) Has this invariant been studied before, and if so, what is the terminology used for it?

I am fairly sure that the general answer to the main question is strongly related to the characterization (and in particular the disjointness) of the sets of forbidden minors of the following two sets (which are almost certainly not known in general as the Robertson-Seymour theorem is non-constructive):

$\bullet$ Graphs which are $L$-lessly embeddable for a given chiral knot $L$

$\bullet$ Graphs which are $L^+$-lessly and $L^-$-lessly embeddable for a given chiral knot $L$ with chiralities $L^+$ and $L^-$

Note that graphs in the second set may admit embeddings in $\mathbb{R}^3$ containing either $L^+$ or $L^-$, but have at least one embedding which does not contain both $L^+$ and $L^-$. As of yet, I have not been able to flesh out a proof using this approach however.

For those who don't want to search for the solutions I found, for the left trefoil the points of $C_7$ are connected in the following order:

$p_1 \rightarrow p_3 \rightarrow p_5 \rightarrow p_7 \rightarrow p_2 \rightarrow p_4 \rightarrow p_6 \rightarrow p_1$

For the right trefoil the points of $C_8$ are connected in the following order:

$p_1 \rightarrow p_3 \rightarrow p_7 \rightarrow p_5 \rightarrow p_2 \rightarrow p_8 \rightarrow p_4 \rightarrow p_6 \rightarrow p_1$

EDIT: Here are pictures of these two projections to help clarify the situation:

https://docs.google.com/open?id=0B5BVGcL23IkoSTlNNGZKZnZtT1E

With regards to Dylan's question about how this projection arose, I was considering the parametric curve $S(t) = (t,t^2,t^3) \subset \mathbb{R}^3$. In a comment or answer on a past MO post which for the love of me I cannot find now, someone had shown in a very simple way that no two chords of $S$ intersect one another anywhere in $\mathbb{R}^3$ (unless they share an endpoint). Thus, for each $n$, $K_n$ can be embedded in $\mathbb{R}^3$ as the set of chords connecting the points $(1...n)$. Now for a fixed tame knot or link $K$, the Robertson-Seymour theorem implies there is a finite set of forbidden minors for graphs which are $K$-lessly embeddable. Hence, every embedding of $K_n$ for $n$ sufficiently large contains $K$, so one may ask (like I did) "what $n$ is sufficient for a given $K$, and what order must I connect the points $(1...n)$ in order to realize $K$?" The crossing condition comes from looking at the chords projected onto the $yz$-plane as viewed from the $-x$ direction (which I think is the direction I did my crossing calculations from). Finally, I moved the $yz$-projections of the integral $t$-valued points around so that they lay on the unit circle to make the pictures easier/clearer.

UPDATE: I was just skimming through a paper on some results on knots which were unrelated to this one. That paper referenced the Ramsey number $r(L)$ of a link $L$, and upon following its references I found this paper which proves the existence of $r(L)$ using essentially the representation I layed out above:

http://www.ams.org/journals/tran/1991-324-02/S0002-9947-1991-1069741-9/S0002-9947-1991-1069741-9.pdf

So it would appear the answer to Question 2 is this is known (in at least one paper) as a plat representation (much to my surprise, Negami derives the existence of such representations using essentially the argument I gave above). So that would seem to settle this thread entirely...

Answer by ARupinski for Partitions of an interval

2012-04-15T03:14:41Z

Unless I'm misunderstanding your defintion of having an 'next' interval to the left or right, what about a Cantor set like construction: divide (0,1) into three equal intervals. Let $(\frac{1}{3},\frac{2}{3})$ be included in your decomposition, then divide $(0,\frac{1}{3})$ and $(\frac{2}{3},1)$ into three equal intervals, keeping the middle one of each and further subdividing the left and right pieces. Repeating this process ad nauseum gives a decomposition of (0,1) such that no interval has a nearest neighbor on either side but whose closure is all of (0,1).

Answer by ARupinski for Simple question in the representation of SL(2,C)

2012-01-24T12:44:52Z

This is a bit of expansion on the answer of Mike Skirvin; in particular it gives one way of explicitly calculating the combinatorics involved. My previous answer, although correct in its result, is horribly roundabout and overly computational, a mathematical Rube Goldberg machine if you will; so after waking up this morning I realized there is a much easier approach using a recursion on Symmetric powers.

Define:

$L = U^3 + U + U^{-1} + U^{-3}$

$M = U^4 + U^2 + 2 + U^{-2} + U^{-4}$

Now define a sequence $S_i$ by:

$S_{-2} = 0$

$S_{-1} = 0$

$S_0 = 1$

$S_1 = L$

$S_k = L\cdot S_{k-1} - M\cdot S_{k-2} + L\cdot S_{k-3} - S_{k-4}$ for $k\geq 2$.

Note that the exponents of $U$ in $S_1$ are exactly the weights mentioned by Mike in his comment (1). It turns out the same is true for all the $S_k$: the exponents of $U$ in $S_k$ are exactly the set of weights of $Sym^k(Sym^3(V))$ and the coefficient of $U^\ell$ is exactly the multiplicity of the weight $\ell$ in $Sym^k(Sym^3(V))$.

From this, you can pick out the subrepresentations by looking at where coefficients change; since the weights of any $Sym^\ell(V)$ occur with multiplicity 1, the only time the coefficients change is when a new summand occurs.

For example, working out $Sym^3(Sym^3(V))$ one gets the following expression:

$U^9 + U^7 + 2U^5 + 3U^3 + 3U + 3U^{-1} + 3U^{-3} + 2U^{-5} + U^{-7} + U^{-9}$

For the module corresponding to the leading coefficient, subtract 1 from each exponent giving a copy of $Sym^9(V)$ and leaving:

$U^5 + 2U^3 + 2U + 2U^{-1} + 2U^{-3} + U^{-5}$

Repeat this process to pull out a copy of $Sym^5(V)$ and finally a copy of $Sym^3(V)$; there are no more terms left, so this is the complete decomposition of $Sym^3(Sym^3(V))$. In general, the expression for $Sym^k(Sym^3(V))$ in $U$ so obtained is of the form:

$a_0U^{3k} + a_2U^{3k-2} + a_4U^{3k-4} + ... + a_4U^{-3k+4} + a_2U^{-3k+2} + a_0U^{-3k}$

Then $a_0 = 1$ by Mike's comment (2) and the multiplicity of $Sym^\ell(V)$ for $\ell\geq 0$ in the decomposition is just $(a_\ell - a_{\ell+2})$ and the multiplicity of $Sym^{3k}(V)$ is 1 since $a_{-2} = 0$.

As for the recursion, it ultimately expresses symmetric powers in terms of lower symmetric powers and exterior powers; this can be proven using multiplication of Young diagrams and inclusion-exclusion although I don't have a good reference at hand.

Answer by ARupinski for Decompose tensor product of type $G_2$ Lie algebras.

2012-01-14T00:20:38Z

The search term you want to look for is "Klimyk's Formula." This formula boils down to the following:

Fix $G$ a compact complex semisimple Lie group. Suppose $V(\lambda)$ and $V(\mu)$ are irreducible representations with highest weights $\lambda$ and $\mu$ respectively. Let $W_\lambda = {\lambda_1,\lambda_2,\ldots \lambda_d}$ be the multiset of weights of $V(\lambda)$ with $d = dim(V(\lambda))$. Then the irreducible components of $V(\lambda)\otimes V(\mu)$ are given by ${V(\mu+\lambda_i)}_{i=1}^d$.

To apply this in practice, you need to be comfortable with the concept of defining $V(\lambda)$ when $\lambda$ is not a dominant weight (which sometimes causes modules to cancel when they appear with both positive and negative signs in the sum), but it applies to lots of groups (even beyond the scope of compact complex semisimple in some cases if im not mistaken), and Littlewood-Richardson is just the special case of this formula in type $A$.

An example for $G_2$ (since that is also my favorite compact semisimple Lie group) is to let $\lambda = [1,0]$ be the highest weight of the 7-dimensional representation and $\mu = [0,1]$ the highest weight of the 14-dimensional adjoint representation.

The seven weights of $V(\lambda)$ are $[1,0]$, $[-1,1]$, $[2,-1]$, $[0,0]$, $[-2,1]$, $[1,-1]$, and $[-1,0]$ so Klimyk tells us the 98-dimensional tensor product decomposes as:

$V([1,1]) \oplus V([-1,2]) \oplus V([2,0]) \oplus V([0,1]) \oplus V([-2,2]) \oplus V([1,0]) \oplus V([-1,1])$

This is where familiarity with interpreting modules with non-dominant highest weights comes in; $V[-1,2]$ and $V[-1,1]$ turn out to be 0-dimensional modules, while $V([-2,2]) \cong -V([0,1])$*. Thus the terms which do not disappear are $V([1,1])$ which is a 64-dimensional module, $V([2,0])$ which is a 27-dimensional module, and $V([1,0])$ which is the 7-dimensional defining representation, a total of 98 dimensions.

If you had instead chosen to switch $\lambda$ and $\mu$ and add the 14 weights of $V([0,1])$ to [1,0], you would have obtained 14 modules, but as before, some would have been zero and others would have cancelled in pairs ultimately leading to the same three modules as above being the only things left over. In my opinion, this reflexivity always holding is the coolest thing about Klimyk's formula.

One neat corollary to Klimyk's formula is that a tensor product of two irreducible modules cannot decompose into a sum of more than $d$ irreducibles where $d$ is the minimum of the dimensions of the two modules.

*EDIT: After posting, I decided to add a bit more about modules with non-dominant highest weight. Basically, the weights of a group $G$ are permuted via the Weyl group action on the weights. Weights are determined by integer $r$-tuples where $r$ is the rank of $G$; tuples containing a -1 lie in the walls of the Weyl chambers and so the modules with these highest weights end up being 0. There are a few other subspaces which also correspond to walls; weights $\mu$ not lying in the walls satisfy $w(\mu) = \lambda$ for some dominant weight $\lambda$ (all coordinates nonnegative) and a unique $w$ in the Weyl group (i.e. only one $w$ in the Weyl group will take $\mu$ to a dominant weight, so $\lambda$ is also uniquely determined). Then $V(\mu)$ is defined by the following relationship:

$V(\mu) = (-1)^w\cdot V(\lambda)$

Here $(-1)^w$ is the sign representation which appears with all Weyl groups; in the $A$-series whose Weyl groups are the $S_n$'s this is the ordinary sign representation.

Generalization of a Result on Solvable Groups

2011-12-15T22:35:37Z

This question concerns finite groups.

It is a well-known fact that every subgroup of a solvable group must again be solvable; this is easily proven by looking at the derived series of a given subgroup.

What I have been thinking about for awhile now is if/how this generalizes to arbitrary finite groups? Specifically, given some set $S$ of finite simple groups, consider the set $\Gamma_S$ of all finite groups whose composition series only includes groups in $S$. Then the above statement on solvable groups can be rephrased as:

THEOREM: Let $S = \{ \mathbb{Z}/p\mathbb{Z}\}_{p\in P}$. If $G\in \Gamma_S$ then $\forall H \leq G$ one has $H\in\Gamma_S$.

Trying to generalize to arbitrary $S$, the obvious generalization to try is:

CONJECTURE (1): For $S$ an arbitrary set of finite simple groups, if $G\in \Gamma_S$ then $\forall H \leq G$ one has $H\in\Gamma_S$.

Unfortunately, this is easily seen to be false; let $S = \{A_6\}$. Then $A_6\in \Gamma_S$ but $A_5\leq A_6$ and $A_5\notin \Gamma_S$. The failure in this example then leads me to the following second attempt at a generalization:

CONJECTURE (2): Let $S$ be an arbitrary set of finite simple groups, and $c(S)$ denote the set of all finite simple groups which appear as composition factors of some subgroup of some element of $S$. If $G\in \Gamma_S$ then $\forall H \leq G$ one has $H\in \Gamma_{c(S)}$.

I have been trying to figure out how to prove Conjecture (2). One thought is to use some appropriate analogue of the derived series for the general case, although coming up with the right analogue seems elusive. I have also thought about using the characters of elements of $S$, but this too does not lead to any immediate insights.

So, does anyone know whether Conjecture (2) is indeed true, and if so have either a (short enough for a post) proof or reference to where this question or similar ones might have been considered before?

Some questions concerning a random number process

2011-10-28T11:36:06Z

Consider the following Markov process: Start with an integer $N = N_0$. Now repeatedly choose an $N_i$ uniformly at random in the range $[1...N_{i-1}]$ until $N_i = 1$ at which point one terminates the process. This produces a nonincreasing integer sequence ${N_0,N_1,\ldots,N_{k-1},N_k = 1}$.

Experimental evidence shows that as $N_0$ grows large, the expected length $E(N_0)$ of such a sequence seems to approach $ln(N_0)$. Equivalently, one expects that the average over many steps of $N_i/N_{i+1}$ is approximately $e$. Convergence to this expectation is slow however; for example if $N_0$ is a 1000-bit integer one finds that $E(N_0)$ satisfies roughly $2.71^{E(N_0)} = N_0$ and in particular the base agrees with $e$ to only around 2 decimal places.

Because the $N_i$ were chosen uniformly at random, for any given $i$ the expectation of $N_i/N_{i+1}$ is 2, so this seems to contradict the above observation that the average of $N_i/N_{i+1}$ is approximately $e$. To understand this discrepancy, consider a toy example where $N_1 = qN_0$ and $N_2 = (1-q)N_1$ for some $0\leq q\leq 1$. One sees that $N_2 \leq \frac{1}{4}N_0$ with equality iff $q=\frac{1}{2}$; clearly the average of the step ratios $q$ and $1-q$ is equal to the expected single step ratio $\frac{1}{2}$, but the composition of the steps has led to an overall decrease in the sequence at a rate faster than division by 2. Hence the above observation that the overall step decrease rate is approximately division by $e$ is plausible.

Main Question: How does one understand the appearance of $e$ in the expected step down rate (as opposed to some other constant)? Presumably it should appear as a result of some averaging of all possible step ratios, but I can't seem to see what the correct average to be considering is.

Secondary question: At the risk of being vague, does anyone know what an inverse to this process looks like? That is, a process where $M_0 = 1$ and at each step one chooses an $M_i\geq M_{i-1}$ at random such that the expected growth rate is roughly multiplication by $e$ but such that the expected growth at any step should be multiplication by 2. Clearly one cannot choose the next number uniformly at random since this would lead to infinite step and expected growth, so what probability distribution (if any) can be put on the integers greater than $N_i$ so that choosing a next element will lead to a process which looks roughly like the original process in reverse?

Is there an easy description of the structure of this infinite group?

2011-09-19T15:35:39Z

Let $S_\infty$ denote the full symmetric group on countably many points and index the points by $\mathbb{N}$. For any weight (for lack of a better name) function $w:\mathbb{N}\rightarrow\mathbb R^+$, define a subgroup $S_\infty(w)\subset S_\infty$ as follows:

$$S_\infty(w) := \{\pi\in S_\infty|\sum_{\pi(k)\neq k} w(k)<\infty \}$$

The intuitive idea is that given a weight function $w$ a permutation $\pi\in S_\infty$ is in $S_\infty(w)$ if the sum of the weights of all points moved by $\pi$ is finite.

There are two well-known examples of such subgroups:

$S_\infty(1)$ is the group of finitely supported permutations of $\mathbb{N}$ or equivalently the direct limit of the finite symmetric groups.
$S_\infty(\frac{1}{n^2})$ is simply $S_\infty$ since the series $\{\frac{1}{n^2}\}$ is convergent.

So in this context, I have been thinking about the group $G := S_\infty(\frac{1}{n})$. It is clear $S_\infty(1)\not\cong G$ since $G$ contains many subgroups isomorphic to $S_\infty$ (for example the set of all permutations of the points indexed by $b^i$ for $b$ fixed and $i\in\mathbb{N}$).

On the other hand, ~~$G$ contains a proper subgroup isomorphic to the direct sum of countably many copies of $S_\infty$, so in particular~~ it is easy to see $S_\infty\not\cong G$ since in $G$ elements of infinite order always have nontrivial centralizers while in $S_\infty$ this is not always the case.

Question: Aside from the description of $G$ as $S_\infty(\frac{1}{n})$, is there any easy to describe/understand presentation of this group?

Primarily I am torn on whether $G$ is itself isomorphic to a direct sum of countably many copies of $S_\infty$; every time I attempt to describe such an isomorphism, there are elements of $G$ not accounted for.

Answer by ARupinski for Examples of seemingly elementary problems that are hard to solve?

2011-09-18T02:06:43Z

One simple to state problem in number theory is the Collatz Conjecture, and I'm kind of surprised no one has mentioned this one yet (considering the examples you cite, I suspect it is because this one does not require anything beyond grade-school math to understand and so may seem below the level of this question). Nevertheless I add it to the list because it is amazingly addictive to think about.

To what extent can one prescribe degrees of irreducible representations of a group?

2011-09-12T15:58:37Z

Suppose one starts with an (infinite) multiset of positive integers $\mathcal{A} = \{a_i\}_{i\geq 0}$ such that:

$1=a_0\leq a_1\leq a_2\leq\ldots$

Can one always find a (necessarily infinite) group $G$ such that the set of degrees of its finite dimensional irreducible complex representations is exactly $\mathcal{A}$?

Clearly the answer to the above question is no for arbitrary $\mathcal{A}$; for example if $a_1 = N>1$ (i.e. the trivial representation is the only 1-dimensional representation of the potential group), then a simple argument involving the decomposition of the tensor square of this $N$-dimensional representation shows that $N\leq a_2\leq \frac{N^2+N}{2}$. Using more general forms of such arguments involving tensor powers of decompositions of $GL_n(\mathbb{C})$-representations, one can find other restrictions ruling out certain potential degree sequences.

$\bf{Question:}$ Given $\mathcal{A}$ such that there are no obstructions arising from tensor power considerations, is it always possible to find/construct a group $G$ whose irreducible degree sequence is exactly $\mathcal{A}$?

I assume that in general this is still a hard question, so I am also interested in partial results. I would also be interested in negative results along the lines "Even though this sequence $\mathcal{A}$ has no obstructions, it still cannot be the degree sequence of any group for some deeper reason."

Answer by ARupinski for free group of finite rank can contain free groups of infinite rank as a subgroup

2011-09-08T18:34:33Z

In case an explicit description of such a subgroup would help, let $F_2 = \langle a,b|\rangle$ be the free group on 2 generators. Then the subgroup generated by the elements $\{a^nb^n\}_{n\in\mathbb{N}}$ is free since it is a subgroup of a free group. Next, it is easy to check that the generator $a^kb^k$ is not an element of the free group generated by the $a^\ell b^\ell$ for $\ell\neq k$ so one concludes that this subgroup has infinite rank.

Answer by ARupinski for Multiplying functions on the unit square as generalized matrices

2011-09-04T04:28:01Z

This is a partial answer concerning the determinants of such objects. While Will Jagy is right that such objects will have an uncountable spectrum, there still may be some hope for assigning a determinant in some cases as follows. First there is one obvious candidate of a trace for such objects: $Tr(F) = \int_0^1 F(t,t)dt$ (Note that the Identity does not have trace equal the dimension of the matrix under this definition, but this definition parallels your approach of replacing all finite summations with integrals). Then in analogy with finite-dimensional matrix theory, the $k^{th}$ powersum of the spectrum of $F$ should be $Tr(F^k)$. Now using the Newton identities, one can recursively construct the sequence of elementary symmetric functions of the spectrum of $F$.

On the one hand, for ordinary matrices $M$ acting on a vector space $V$ of dimension $d$, the elementary symmetric function $e_i$ evaluated on the eigenvalues of $M$ is equal to the trace of the operator defined by the action of $M$ on $\Lambda^i V$. In particular, $\Lambda^d V$ is one-dimensional and therefore the action of $M$ on this space is simply a scalar, this scalar is exactly $e_d = det(M)$.

In your case, your generalized matrices act on an infinite-dimensional function space $V$ and $\Lambda^\infty V$ does not make sense. Nevertheless, combining the earlier definition of the trace of $F$ with the interpretation of the elementary symmetric functions above, we therefore have the following candidate for a determinant of such a generalized matrix $F$ (provided the limit exists):

$Det(F) = \lim_{i\rightarrow\infty}e_i(F)$

Where:

$e_1(F) = Tr(F)$

$e_2(F) = \frac{1}{2}\left(e_1(F)\cdot Tr(F)-Tr(F^2)\right)$

$e_3(F) = \frac{1}{3}\left(e_2(F)\cdot Tr(F)-e_1(F)\cdot Tr(F^2)+Tr(F^3)\right)$

$\ldots$

Of course the difficulty in this approach lies in efficiently calculating the $e_i(F)$ and showing the above limit exists. Thus you might need to assume some additional constraints to make this approach work.

Subdivision of triangles into congruent triangles

2011-06-08T02:02:03Z

Recently some old notes of mine have gotten me to thinking about the problem of subdividing a triangle into $N$ smaller triangles, all congruent to one another. A little thought shows the following are possible values of $N$:

$\bullet$ If $N$ is a perfect square then any triangle can be subdivided into $N$ such smaller triangles

$\bullet$ If $N$ is a sum of two squares, say $N = a^2+b^2$ then a right triangle with side lengths in the ratio $a:b:\sqrt{a^2+b^2}$ can be subdivided into $N$ smaller triangles

$\bullet$ If $N=3$ then a $30-60-90$ triangle admits a decomposition into 3 congruent triangles

$\bullet$ Furthermore, by iterating the subdivisions indicated above, one can also obtain such subdivisions for any $N$ of the form $3^k\cdot m^2$

Question 1: Are the values of $N$ listed above the only ones possible if one requires the subtriangles be similar to the original triangle?

Question 2: In each of the examples above, the subtriangles formed are always similar to the original triangle. Does the answer to Question 1 change if one no longer requires that subtriangles be similar to the original triangle. (For example, if one does not require that the subtriangles are congruent to the original triangle, then an equilateral triangle may be subdivided into 3 congruent copies of a 30-30-120 triangle)

Appearances of 'exotic' compact Lie Groups

2011-05-19T19:06:40Z

The structure theorem for compact Lie Groups states that all compact Lie groups are finite central quotients of a product of copies of $U(1)$ and simple compact Lie groups. And yet, as easy as arbitrary compact Lie groups are to describe, most Lie Groups one encounters are the various quotients of simple compact Lie groups and maybe some products of these groups (I will herein refer to such groups as standard Lie groups). The only compact examples which one encounters regularly that are not standard Lie groups are the unitary groups $U(n)$ (which are quotients of $U(1)\times SU(n)$) and $SO(4)$ (which is the diagonal $\mathbb{Z}/2\mathbb{Z}$ quotient of $Spin(4) \cong Spin(3)\times Spin(3)$).

I am currently trying to further expand my knowledge and understanding of compact Lie groups, so I am wondering:

Question: Has anyone encountered examples of non-standard Lie groups (other than the $U(n)$'s and $SO(4)$) in their research, as the autormorphism group of some object they were studying, or in some other way? If so, would you give a bit of description of the setting you were working in as well as a description of the non-standard group which appeared?

Although given a non-standard group, one can easily construct algebraic objects for which it is the automorphism group, I am more interested in instances of the reverse of this process wherein a non-standard group appears in the course of thinking about some other problem.

Edit: Since there still seems to be some misunderstanding of the intent of the question, to clarify the situation I am interested in, I am looking for groups of the form $G_1\times\ldots\times G_k/H$ where each $G_i$ is a compact simple Lie group, $k\geq 2$ and $H\subsetneq Z(G_1\times\ldots\times G_k)$ is not of the form $h_1\times \ldots \times h_k$ with $h_i\subseteq Z(G_i)$. So examples with multiple factors such as the the Structure Group of the Standard Model described by Theo are the sort of thing I'm looking for.

Occurence of trivial representation in a tensor square.

2011-05-13T19:21:53Z

Suppose $G$ is a group and $V$ an irreducible representation of $G$. One has that $V\otimes V\cong \Lambda^2(V)\oplus Sym^2(V)$. It is well-known that if the trivial representation appears as a subrepresentation of $\Lambda^2(V)$ then $V$ is of quaternionic type; while if the trivial representation appears as a subrepresentation of $Sym^2(V)$ then $V$ is a of real type. From this approach, it is clear that the trivial representation cannot appear in both $\Lambda^2(V)$ and $Sym^2(V)$.

What I am curious about is as follows:

Question: Is there is some (relatively easy) way to see why the trivial representation cannot appear in both $\Lambda^2(V)$ and $Sym^2(V)$ without introducing the machinery of real/quaternionic types?

As a bit of motivation, if one looks at other subrepresentations, then for example if $G = G_2$ and $V_n$ is an $n$-dimensional irreducible representation of $G_2$, then $V_{64}$ appears as a subrepresentation of both $\Lambda^2(V_{27})$ and $Sym^2(V_{27})$. In particular it is possible for the intertwining number of $\Lambda^2(V)$ and $Sym^2(V)$ to be nonzero, but by the real vs. quaternionic characterization, the trivial representation is somehow special in that it cannot contribute to the intertwining number.

Answer by ARupinski for The first eigenvalue of a graph - what does it reflect?

2011-05-02T14:20:37Z

The few times I have ever worked with eigenvalues of graphs, it has been in relation to the path algebra of the graph; each path in the graph is an element of this algebra. At any rate, the characteristic polynomial of the graph gives exact recurrences for calculating the number of paths of a given length and in particular the largest eigenvalue will give the asymptotic growth rate of the number of paths of different lengths. This asymptotic growth is true if the largest eigenvalue has modulus larger than all other eigenvalues of the graph. If there are multiple eigenvalues of maximum modulus then the asymptotics of the path-growth function will change although offhand I don't know if having multiple eigenvalues of the same maximal modulus is actually possible (perhaps someone who does more graph theory than I would care to comment on this).

Comment by ARupinski

2013-06-15T01:27:45Z

Note that your second sequence $\\{2, 0, 2, 4, 10, 24,\ldots\\}$ is just the doubles of your first sequence, shifted right by one step. So it probably would not appear in the OEIS.

Comment by ARupinski

2013-06-13T01:56:53Z

Note that this is a rewrite of my original answer to correct the cycle condition which I had misstated as pointed out by the OP.

Comment by ARupinski

2013-06-13T01:08:38Z

Ahh, I see the issue. When I originally was constructing the bijection, I thought it was necessary to have the fixed points. But what it looks like I really want for the bijection is just that the steps of the descent mark the right endpoints of the cycles of $\psi$. Will edit the answer to remove this issue.

Comment by ARupinski

2013-05-08T00:04:12Z

@Gerry Myerson: thanks for clearing that up. Obviously I read the formulation through too quickly without thinking about what it was asserting.

Comment by ARupinski

2013-05-06T23:28:31Z

You claim that this is true for $m < 10^8$, but why does for example $m = 32$ work? I have that $f(32\times 32) = 4201 \neq f(32)\times f(32) = 529$ even though for 32 one has $a_0,a_1\in\{0,1,2,3\}$. Is there an extra assumption that is missing here?

Comment by ARupinski

2013-05-04T00:37:30Z

@Benjamin: I had thought about that sort of approach too, but how do you ensure that your 4-in-a-rows so that they align with each other (i.e. why can P2 not see this strategy and play to block the 4-in-a-rows that you need, forcing you to form one not aligned with your previous 4-in-a-rows)? Is there a good way to force P2 to only block certain potential 4-in-a-rows so that P1 eventually gets a 5-in-a-row?

Comment by ARupinski

2013-05-02T22:06:17Z

Also by playing his points so that intersections of any of the lines he forms do not coincide with any of P2s already played points, it is obvious that by move 5 P1 has too many double 3-in-a-rows lined up for P2 to stop them all with just one point.

Comment by ARupinski

2013-05-02T22:04:42Z

@Ricky: So maybe he needs one more move then... if P1 always plays his points such that they are not collinear with any pair of points already on the plane, then even if P2 has blocked 2 of the potential 3-in-a-rows on the Fano configuration, P1s fifth point will form several new partial Fano configurations; by this point there are 10 different lines formed by the pairs of P1s points; each of these lines intersects one another somewhere in the plane and at most 3 of P2s points are on any of these lines (P2s first point does not help P2 in any way because of P1s non-collinearity strategy).

Comment by ARupinski

2013-05-02T02:03:42Z

So no matter how P2 responds now, at least one of the edge points of this Failed Fano configuration is open, so P1 forms two 3-in-a-rows simultaneously, thereby foiling any further attempt by P2 to win. I don't see any good way to extend this approach to $n>4$ (on account of the rather special nature of the Failed Fano configuration), but maybe this sparks an insight by someone else for the general case...

Comment by ARupinski

2013-05-02T01:57:27Z

For $n=4$ a similar approach should work. P1 can always play his 2nd and 3rd points into a triangle with at most one of its edges containing one of P2s first two points. Now no matter how P2 chooses to block one of these edges, P1 can find a point such that none of the lines connecting that point to his previous 3 points contain any of P2s points thusfar and which is not collinear with any pair of his previously placed points. Note that P1s points now form the 3 vertices and center point of the Failed Fano configuration.

Comment by ARupinski

2013-01-30T04:38:01Z

Your question seems to be covered by the comments and answers to [mathoverflow.net/questions/62088/…. And unless I misunderstand what you are asking in (2), there is no way $\Phi$ can be surjective for an entire range of $\alpha$'s if it fails to be surjective for some $\alpha$ in the given range.

Comment by ARupinski

2013-01-23T22:51:21Z

See primes.utm.edu/notes/faq/NextMersenne.html and some of the linked pages; in particular there are conjectures about the log distributions of Mersennes and some supporting evidence.

Comment by ARupinski

2013-01-21T16:35:05Z

The covering sequence can then be taken as the $a_i$ and the sequence of cofactors can be taken as the $b_i$ which then gives a solution to your particular problem.

Comment by ARupinski

2013-01-21T16:34:15Z

@Antisha: Ronald Graham's 1964 paper "A Fibonacci-like sequence of composite numbers" shows how to construct a linearly recurrent sequence all of whose entries are composite numbers using the Fibonacci recurrence. By modifying his approach it should be possible to find a covering sequence for this recurrence, (although there may be some complications I don't immediately see due to the fact that here the associated polynomial $x^2-3x+2$ factors while for the Fibonacci sequence the associated polynomial $x^2-x-1$ does not factor).

Comment by ARupinski

2013-01-20T22:16:14Z

There also seem to be examples with infinite degree vertices, so perhaps total classification might be out of reach, but classification of those with only finite degree vertices might be doable. I am definitely going to think about this some more.