User - MathOverflow

Have any publications been made in this area of group theory?

2012-01-25T23:32:06Z

For a group $G$ and a tuple $J = (g_1,g_2 ... g_n) \in G^k$ for $k$ some constant, define a parametrized word $w : G^k \rightarrow G$ to be a function which takes $J$ to some product of the elements in $J$. So $w(J) = g_1g_1g_2$ for $k \geq 2$ would be an example.

The structure of the space of all $w$ for a particular group modulo the equivalence relation of functional equality is not trivial. For instance, over $\mathbb{Z}_2$, $g_1g_1g_2 = g_2$ for all $J$ ,and for a finite abelian group the space of $w$ is clearly finite.

I don't know whether this topic has been covered before; It seems simple enough that someone might have done work on it, but I cannot find anything. Does anyone know what this area might be called?

Rigorous proof of the duality of Coupon collector's problem and Occupancy problem

2012-04-03T15:49:48Z

We have $k$ different types of coupons (with replacement).If we collect at least $l$ different coupons, we win a prize. We can only afford to collect $m$ coupons.

Let's say we take all those $m$ coupons, and we collect exactly $L$ different coupons. Then the probability that we win a prize is $P(L \geq l)$

Let $T$ be the number of trials taken to collect exactly $l$ coupons. Then the probability we win a prize is $P(T \leq m)$

"Clearly" $P(L \geq l) = P(T \leq m)$.

So how on earth does one go about proving it rigorously? I'm not too familiar with the theory of stopping times, and the proof may come from that area, but no treatise that mentions these two problems ever seems to prove this equality. Does anyone know of someone that has taken the time to prove this rigorously, and what formalism that they use?

Typographically separating logical argument from explanation and example

2012-03-22T22:28:59Z

I am currently writing a master's dissertation. In this dissertation I have chosen to typographically separate logical argument, (Theorems, Proofs, and Definitions) from aids to understanding (Examples, Remarks and Asides).

Basically, sections that are intended to be rigorous is written in normal font, and sections that are intended to help the reader understand what is being written, but are not fundamental are written italicised.

The intention is simple: One who is familiar with the area is likely only checking definitions or theorems, and can focus on the normal text without hunting through a mountain of prose that they are already familiar with.

Someone who is new to the area, and who is not yet interested in the nitty-gritty details of a formal definition can focus on the italicised text, perhaps going back to the normal text later for something more concrete.

However my supervisor seems to think this is a bad idea, and has asked me to find precedents for this from well-known authors. Has anyone seen something like this before?

PS. When i say italicised, i actually mean only slanted. It's much easier to read than actually-italicised text. I could change the font to sans-serif for those sections.

Results in the Presentation of Finite Groups

2012-03-07T21:31:27Z

I've been looking at combinatorial group theory, but all the results seem to be about infinite groups. Are there any important results about the presentations finite groups specifically (or are useful for finite groups?). About how the minimum number of relations implies something about the structure of the group?

I'd prefer results that are applicable to all finite groups or to all finite simple or all simple groups.

A programming language that can only create algorithms with polynomial runtime?

2012-02-04T01:55:19Z

Has someone constructed a programming language that can construct all the algorithms in P, and no others?

I'm interested in this restriction coming from the syntax naturally, as opposed to just being a normal Turing machine with a step-timer attached.

Comment by

2012-04-15T09:52:59Z

For some reason i can't edit, but the range in question is $[0,1)$ and the digital representation is all those digits occurring after the decimal point.

Comment by

2012-04-15T09:51:03Z

I might add that you can instead define the probability space to be the reals $[\0 \ldots 1)$. Then for a particular real you take it's digital representation in base $k$ as your sequence. This is essentially the same as your answer, except you get the structure of the sigma-algebra and probability space "for free".

Comment by

2012-04-03T19:38:47Z

Okay then, what is the sample space that these events are defined over? T and L can be described as random variables over the set of all sequences of picks which is uncountable and un-measureable. Though i suppose i could truncate it to all sequences of length m and allow T to be "Never". But then we can't define its variance or expectation, and its those that i am interested in.

Comment by

2012-03-23T11:36:34Z

Sans-serif is fine. I'm more interested in the citation that typographical advice though.