## graphs – Representation of connected components in the \$O(|E|)\$ time/space variant of Karger’s algorithm

I’m trying to understand the various optimizations given in the original 1992 paper on Karger’s algorithm. Specifically, looking at section “3.1 Unweighted Graphs”, I don’t understand what data structure is used to represent the variant of the algorithm that works in $$O(|E|)$$ time and space (the other variant, which uses union-find and takes $$O(|V|)$$ space and $$O(|E| log |E|)$$ time, makes sense).

Specifically: how would you represent the edges so that it is possible to

1. track the connected components induced by a sequence of $$m$$ edges in a random order in $$O(m)$$ time?
2. contract a sequence of $$m/2$$ edges in a random order in $$O(m)$$ time?

I must be missing something obvious, but I couldn’t find any implementation for this variant (everyone seems mostly interested in implementing the union-find variant of the algorithm).

Posted on Categories Articles

## analytic number theory – Proving Integral representation of \$zeta(n)\$

Currently studying analytic number theory and was baffled by the following integral representation of $$zeta(n)$$

$$zeta(n) = dfrac{2}{1 – 2^{1 – n}}sinleft(dfrac{pi n}{2}right)int_0^infty dfrac{x^{-2n}}{pi x}(1 – pi x^2csc(pi x^2))dx$$

However there’s no proof for this provided in the text.

Any help or hints would be highly appreciated.

Thanks.

Posted on Categories Articles

## ra.rings and algebras – Representation theory terminology question

For a paper I’m writing, I need a term for a representation-theoretic concept that I’m sure someone has thought of before, so I thought I’d ask here rather than just make something up.

Let $$G$$ be a group and $$R$$ be a commutative ring. Consider an $$R(G)$$-module $$V$$. For any ideal $$I$$ of $$R$$, we have the submodule
$$I V = {text{c cdot v | c in I and v in V}}.$$
What is the term for $$R(G)$$-modules $$V$$ such that all submodules are of this form? The ones I’m interested in have the additional property that if you ignore the $$G$$-action, then they are free $$R$$-modules (though not finitely generated!), but I doubt this matters for this question.

For an easy example, if $$R = mathbb{Z}$$ and $$G = text{GL}(n,mathbb{mathbb{Z}})$$, then $$mathbb{Z}^n$$ has this property.

If $$R$$ is a field, then this reduces the the usual notion of an irreducible representation, so I think of this as a version of irreducibility. But looking through my ring-theory books, I can’t find it anywhere.

Posted on Categories Articles

## gr.group theory – Irreducible Representation of A_5

Knowing the fact that standard representation arising out of permutation representation of $$A_5$$ over $$mathbb{C}$$ is irreducible and of degree $$4$$. What can we conclude about the irreducibility over general field, whose characteristics does not divide the order of $$A_5$$. Is it irreducible ? Can we use Clifford Theory here ? How ?

Posted on Categories Articles

## group theory – How do I find a non-trivial 2D representation of \$Z_2 subset \$ SL(2, C)?

I am trying to find a non-trivial two dimensional representation of $$Z_2 subset SL(2, C)$$, but I am a little stuck.

Here is what I did so far:

For M $$in$$ SL(2, $$Z_2$$):
$$begin{bmatrix}a&b\c&dend{bmatrix}$$
with det M = ad – bc = 1 and a, b, c, d $$in$$ {0, 1}.

I also found that the order of SL(2, Z$$_2$$) is 6.

So putting the pieces together, I think that this means that I am looking for a representation of six 2 x 2 matrices that each have a determinant of +1, where my matrix elements are either 0 or 1.

I found the following 3 matrices that satisfy these conditions
$$begin{bmatrix}1&0\0&1end{bmatrix}$$ $$begin{bmatrix}1&1\0&1end{bmatrix}$$ $$begin{bmatrix}1&0\1&1end{bmatrix}$$

This is where I am stuck: I am unable to find 3 more matrices, only consisting of 0 and 1, that satisfy the condition that my determinant is 1. How do I proceed?

Posted on Categories Articles

## exponentiation – Integral representation of \$f(x)=0^x\$

Recently I had an argument with Luboš Motl on Quora, where he had argued that $$0^0$$ should be left undefined in computer algebra systems, because $$x^y$$ has no limit at $$(0,0)$$ and $$0^x=0$$ at all $$x>0$$.

So, I decided to represent the function $$0^x$$ in integral form. Once heaving a universal representation of the function one would be able to see what its value at $$x=0$$ is (as well as around that point).

For that purpose, I armed myself with divergent integrals, Laplace transforms, etc, etc.

So, assuming that

$$0^{-n}=frac{W^{n+1}-w^{n+1}}{(n+1)!}$$

where

$$w^n=B_n(0)+nint_0^infty B_{n-1}(x)dx$$

and

$$W^n=B_n(1)+nint_0^infty B_{n-1}(x+1)dx$$

I obtained the following formula:

$$0^x=frac{B_{1-x}(1)-B_{1-x}+int_0^{infty } (x-1) x t^{-x-1} , dt}{Gamma (2-x)}=frac{(x-1) zeta (x,1)-(x-1) zeta (x,0)+int_0^{infty } (x-1) x t^{-x-1} , dt}{Gamma (2-x)}$$

The formula with Bernoulli polynomials works well in Mathematica at positive and negative integer $$x$$, returning expected divergent integrals, but the formula with Hurwitz Zeta fails at positive integers, returning expression with the symbol `ComplexInfinity`.

The both formulas fail at non-integer $$x$$. So, I wonder, whether it is possible to re-write these formulas in such a way that I would always obtain a convergent or divergent integral?

I tried to apply the integral representations of Hurwitz Zeta function from Wikipedia, but those return wrong results outside of their range of validity (unlike the built-in functions).

Posted on Categories Articles

## real analysis – Integral representation in the case of two variable function

Let $$fin C^1(mathbb{R},mathbb{R})$$, we have the follwoing integral representation : for all $$a,bin mathbb{R}$$ :
$$f(b)-f(a)=int_a^b f(t)dt.$$
Now if we consider $$gin C^1(mathbb{R}^2,mathbb{R})$$ do we have similar result for the mapping $$g(f(.),.)$$ ?

$$g(f(b),b)-g(f(a),a)= int_a^b f'(t)partial_x g(f(t),t)+partial_y g(f(t),t) dt$$
This is my suggestion.

Posted on Categories Articles

## rt.representation theory – Realizability of a real representation using real cyclotomic coefficients

Let $$G$$ be a finite group and $$rho: G rightarrow GL(d,mathbb{C})$$ an irreducible representation with Frobenius-Schur indicator $$frac{1}{|G|}sum_{gin G} operatorname{tr} rho(g^2) = 1$$. Thus $$rho$$ is a real representation.

A theorem by Brauer states that every irreducible representation over $$mathbb{C}$$ can be written using coefficients taken from $$mathbb{Q}(zeta_n)$$ where $$zeta_n=exp(frac{2pi i}{n})$$ where $$n$$ is at most the exponent of the $$G$$.

We also know that any real representation can be written with coefficients in $$mathbb{R}$$

Can we satisfy both?

For example, the irreducible representations for the dihedral groups can satisfy both conditions (real coefficients using cosines and sines of fractions of $$pi$$).

I can solve the problem over the algebraic integers by computing an antilinear equivariant involution $$F$$ such that $$F(x) = J overline{x}$$ for a suitable matrix $$J$$, and such that $$rho(g) F(x) = F(rho(g) x)$$, which implies $$rho(g) J = J overline{rho(g)}$$. Then I know that $$J overline{J} = alpha mathbb{1}$$ for a positive scalar $$alpha$$, and I set $$J’ = J/ sqrt{alpha}$$, so that $$J’$$ represents the complex conjugation. Now, $$J$$ can be found with cyclotomic coefficients (one iterates over a basis of the space of matrices with $${0,1}$$ coefficients, and averages over the group). But the square root operation is not necessarily closed over the cyclotomics, this is where I am currently stuck.

Posted on Categories Articles

## Representation of Lie algebra to Lie group

Let $$G$$ be a semisimple simply connected Lie group with Lie algebra $$mathfrak g$$ and let $$H$$ be a subgroup of $$G$$ with Lie algebra $$mathfrak h$$. Suppose that I have a finite dimensional highest weight representation $$V$$ of the Lie algebra $$mathfrak g$$ and I restrict this representation to $$mathfrak h$$. Now is the restricted representation is a representation of $$H$$ as well ?

Posted on Categories Articles

## representation theory – Each Weyl group orbit in the character lattice of \$V\$ contains exactly one dominant weight

Let $$V = mathbb{C}^3 otimes mathbb{C}^3$$ be a representation of $$G = SL_3(mathbb{C})$$.
The weights of this representation is the set of $$varepsilon_i + varepsilon_j$$ for $$i, j = 1, 2, 3$$, where $$varepsilon_i$$ takes $$text{diag}(h_1, h_2, h_3) in mathfrak{h}$$ to $$h_i$$.

The Weyl group is $$W = { 1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1 }$$.
For a simple root $$alpha_i$$, the coroot $$h_i$$ is simply the matrix $$E_{ii} – E_{i+1, i+1}$$.
Then the pairing $$langle varepsilon_j, h_i rangle alpha_i = begin{cases} -alpha_i & text{ if } i = j, \ alpha_i & text{ if } i = j -1, \ 0 & text{ else }. end{cases}$$
By the defining equation of root reflections, $$s_i (beta) = beta – langle beta, h_i rangle alpha_i$$ for $$beta in mathfrak{h}^*$$, we have $$s_i(varepsilon_j) = begin{cases} varepsilon_j-alpha_i & text{ if } i = j, \ varepsilon_j + alpha_i & text{ if } i = j -1, \ varepsilon_j & text{ else }. end{cases}$$
Using this last part, the $$W$$-orbit of the weight $$varepsilon_1 + varepsilon_2$$ is the set $${ varepsilon_1 + varepsilon_2, varepsilon_1 + varepsilon_3, varepsilon_2 + varepsilon_3 }$$.

Dominant weights are non-negative integral linear combinations of the fundamental weights, $$mvarpi_1 + n varpi_2$$.
Expanding this out in terms of the $$varepsilon_i$$, I get $$m varpi_1 + n varpi_2 = frac{1}{3} left( 2(m+n) varepsilon_1 + (2n-m) varepsilon_2 – (m+n) varepsilon_3 right).$$
Equating coefficients shows that none of the set of weights $${ varepsilon_1 + varepsilon_2, varepsilon_1 + varepsilon_3, varepsilon_2 + varepsilon_3 }$$ are dominant weights, contradicting what I am supposed to show.
What have I done wrong?

Posted on Categories Articles