User gjergji zaimi - MathOverflow

Answer by Gjergji Zaimi for Trying to solve: Show that n does not divide 3^n - 2^n for n greater than or equal to 2.

2013-05-11T19:46:32Z

Take $p$ to be the smallest prime divisor of $n$. You have that $p$ divides $3^{p-1}-2^{p-1}$ and also $3^n-2^n$. So $p$ divides $3^{\operatorname{gcd}(p-1,n)}-2^{\operatorname{gcd}(p-1,n)}$. However it is easy to see that this gcd must equal $1$, so $p$ divides $3-2$, and we obtain the desired contradiction.

Answer by Gjergji Zaimi for Can a harmonic number be a rational number for non-integer rational argument?

2013-05-07T01:19:07Z

The answer is "no". Your function $H_z$ which is the same as $\psi(z+1)+\gamma$, where $\psi$ is the digamma function, and $\gamma$ is the Euler-Mascheroni constant, takes transcendental values at non-integer rationals. This is a theorem of M. Ram Murty and N. Saradha, "Transcendental values of the digamma function".

Notice that at rational values the digamma function has an explicit evaluation given by Gauss's formula.

Groups, quantum groups and (fill in the blank)

2011-03-10T05:50:10Z

In the study of special functions there are three levels of objects, classical, basic and elliptic. These correspond to classical hypergeometric functions, basic (q-) hypergeometric functions, and elliptic hypergeometric functions.

In combinatorics these notions are related to enumeration, q-enumeration and "elliptic enumeration" (see this article of Schlosser).

Now, I always related the passing to q-analogs by analogy to the "way" one passes from groups to quantum groups. And indeed, q-analogs and quantum groups are not entirely unrelated concepts. But this makes me ask the question in the title, whether someone has considered quantum groups at the "elliptic level", and if so what are they?

Answer by Gjergji Zaimi for Formalization (and background) of a formula, concering the integral points of a polygon.

2013-05-03T06:06:37Z

As the other answer pointed out, this is Brion's theorem, and you can probably find several articles devoted to it. There are many proofs in the literature, the original one using equivariant K-theory and toric geometry, but there are more elementary proofs as well.

My perspective is that Brion's formula gives you an identity of rational functions (or meromorphic functions depending on what polyhedra one considers), which can be obtained by applying the appropriate valuation to a well known geometric decomposition of the polytope.

First let me talk about valuations. The vector space at hand, $\mathbb P$, will be generated by indicator functions of polyhedra with rational coordinates. A valuation will be a linear map to a specified target vector space $V$. There are many useful valuations, such as volume or euler characteristic. The valuation that is relevant here is $$\varphi: \mathbb P\to \mathbb C(x_1,x_2,\dots,x_n)$$ which takes values in rational functions, and which takes a polyhedron to the generating function of lattice points contained in it, whenever this generating function converges, and takes the value zero, otherwise.

Therefore polyhedra containing a line get sent to zero by this valuation. The fact that $\varphi$ is a valuation is not trivial and is attributed independently to Pukhlikov and Khovanskii, "Finitely additive measures of virtual polytopes", and Lawrence, "Valuations and polarity". Notice that if we were to allow irrational polyhedra, we would have to replace rational functions with meromorphic functions.

Now, to the geometric part, we have the following identity of characteristic functions for any polytope $P$ $$\mathbb 1_{P}=\sum_{F \text{ is a face of } P}(-1)^{\operatorname{dim}(F)}\mathbb 1_{T_FP}$$ where $T_FP$ is the tangent cone of $P$ at face $F$. Clearly these tangent cones will contain lines if $\operatorname{dim} F\geq 1$. So the identity $$\mathbb 1_P=\sum_{v \text{ is a vertex of } P}\mathbb 1_{T_vP}$$ holds "modulo lines". And indeed applying the valuation $\varphi$ gives you Brion's formula.

Of course, another important perspective is that Brion's formula is essentially a combinatorial incarnation of the localization formula for equivariant K-theory, so "the right" perspective on this result may vary, depending on who you ask. :)

Answer by Gjergji Zaimi for Estimate on sum of squares of multinomial coefficients

2013-04-23T00:46:44Z

Douglas already commented that the asymptotics for fixed $p$ and $l\to \infty$ shoudl follow from standard methods. One gets $$a_{\ell}^p\approx (p+1)^{2\ell+\frac{p+1}{2}}(4\pi \ell)^{-\frac{p}{2}}.$$ See theorem 4 in "Counting Abelian squares", by Richmond and Shallit. Notice that these numbers appear also in combinatorics when considering abelian squares, or more generally abelian powers, on a fixed alphabet.

For the asymptotics that you're interested in, at least in the unweighted case, one can say $$a _{\ell} ^p=\sum _{j=0} ^{\ell} \binom{p}{j}\sum _{a _1+ \cdots +a _j = \ell \atop a _i \geq 1} \binom{\ell}{a _1,a _2,\dots,a _j}^2$$ which makes it clear that $a _{\ell}^p$ is a polynomial in $p$ of fixed degree $\ell$. The coefficient of $\binom{p}{\ell}$ is $(\ell!)^2$, and the coefficient of $\binom{p}{\ell -1}$ is $\frac{\ell-1}{4}(\ell!)^2$, so you have $$a _{\ell}^p =\ell!p^{\ell}-\ell!\frac{\ell(\ell-1)}{4}p^{\ell-1}+O(p^{\ell-2}).$$

A possible refinement of a theorem of Malliavin

2013-03-08T18:21:16Z

Due to a theorem of Malliavin (an improvement of an erlier theorem of Dixmier and Malliavin, see here) we know that every compactly supported smooth function $f$ on $\mathbb R^n$ can be written as a sum of two convolutions $$f=u_1\circ v_1+u_2\circ v_2$$ where the $u_i,v_i$ are smooth.

Question: Is it known whether we can choose the $u_i,v_i$ to vary continuously with $f$?

The original theorem By Dixmier and Malliavin proves that $f$ is the sum of finitely many convolutions (I believe they prove that $2^n$ is enough). In this case we can choose the functions to depend continuously on $f$, as is proved in this undergraduate thesis.

Malliavin's improvement of the theorem appears in "$C^{\infty}$ parametrix on Lie groups and two steps factorization on convolution algebras", Harmonic analysis (Proc. Conf., Univ. Crete, Iraklion, 1978), pp. 142–156, Lecture Notes in Math., 781, Springer, Berlin, 1980.

Answer by Gjergji Zaimi for Access to a preprint by D. N. Verma

2013-02-28T13:44:11Z

I don't have Verma's preprint, but there are more modern references on the subject, which don't seem to be on OEIS. Basically one looks at the GIT quotient $(\mathbb{P^1})^n//\operatorname{SL}_2$, and your sequence corresponds to its degree under a certain embedding in projective space for values of $n=4,6,8,...$.

See section 2.11 in the paper "The moduli space of n points on the line is cut out by simple quadrics when n is not six", by B. Howard, J. Millson, A. Snowden and R. Vakil. An even more recent reference that also contains a sort of formula for these degrees is "The ring of evenly weighted points on the line", by M. Hering, B. Howard. Hope this helps.

Answer by Gjergji Zaimi for principal specialization of projective Schur functions

2013-02-14T09:33:10Z

There is a very nice specialization when you consider infinitely many variables, due to an identity of Kawanaka: $$Q_{\lambda}(1,q,q^2,\dots)=\prod_{i=1}^m \frac{(-1;q)_{\lambda_i}}{(q;q)_{\lambda_i}} \prod_{1\le i < j \le m} \frac{q^{\lambda_j}-q^{\lambda_i}}{1-q^{\lambda_i+\lambda_j}}$$ where $\lambda$ is a partition of length $m$.

For the case of finitely many variables the story is a little more complicated. In the ordinary Schur polynomial case we have an expression which is a ratio of two determinants and is singular at $(1,1,\dots,1)$, however a Vandermonde factorization helps us get rid of the singularity and obtain an expression in $q$, which is also meaningful when $q=1$.

The same thing can be done with Schur-Q functions. The specialization can be written as a multiple hypergeometric sum, which is singular at $q=1$, but we can find a transformation formula into a hypergeometric sum of Schlosser type which extends to $q=1$. It would be a pain to write out the identities themselves, but if you follow Rosengren's paper on the subject, "Schur Q-polynomials, multiple hypergeometric series and enumeration of marked shifted tableaux", you should have what you want. Combinatorially this is interesting because it gives the $q$-enumeration of marked shifted tableaux.

On a remark of Tait on FLT for the exponent 3

2012-02-01T23:36:07Z

This is one of those recreational questions that aren't really about research. I found a curious remark in an old volume of American Mathematical Monthly (1922) which I'll quote below:

In the Proceedings of the Royal Society of Edinburgh, vol.7, p.144, in some mathematical notes by professor P.G. Tait, it is stated:

"If $x^3+y^3=z^3$, then $(x^3+z^3)^3y^3+(x^3-y^3)^3z^3=(z^3+y^3)^3x^3$.

This furnishes an easy proof of the impossibility of finding two integers the sum of whose cubes is a cube."

How does this "easy proof" follow? Students are notoriously suspicious of those steps which an author announces as "easy", and are sometimes inclined to believe that the word is used in a humorous sense. [...] There are of course proofs in existence that the sum of two cubes cannot be a cube.

Did anyone manage to find a proof of FLT for the exponent 3 using this identity or is the alluded proof another illusion that did not fit in the margin?

Answer by Gjergji Zaimi for A "known" Pythagorean identity in algebra?

2013-02-13T01:32:40Z

These are both simple corollaries of $$\sum_{k\geq 0} t^ke_k(x_1,x_2,\dots)=\prod_{k\geq 0}(1+tx_k).$$

There is a typo in both your identities. They should read, $$(e_0+e_2+\cdots)^2-(e_1+e_3+\cdots)^2=(e_0+e_1+e_2+\cdots)(e_0-e_1+e_2-\cdots)$$ $$=\prod_{k\geq 0}(1+x_k)\prod_{k\geq 0}(1-x_k)=(1-x_1^2)(1-x_2^2)\cdots,$$ and $$(e_0-e_2+e_4-\cdots)^2+(e_1-e_3+e_5-\cdots)^2=(\mathfrak {Re}[\prod_{k\geq 0}(1+ix_k)])^2+(\mathfrak{Im}[\prod_{k\geq 0}(1+ix_k)])^2$$ $$=(1+x_1^2)(1+x_2^2)\cdots$$

Sets of integers represented by degree zero rational functions

2013-01-29T02:54:13Z

Suppose $f(x_1,x_2,\dots)=\frac{P}{Q}$, where $P,Q$ are polynomials in several variables with integer coefficients that have the same degree. Let's denote by $S(f)$ the set of integers $n$ for which $f(x_1,x_2,\dots)=n$ is solvable in integers.

Which sets $S\subset \mathbb Z$ can be written as $S(f)$ for some $f$ as above?

For example we have, $S(\frac{x_1^2+x_2^2}{x_1x_2+1})=\lbrace -5,0,1,4,\dots,k^2,\dots\rbrace$.

This question is just a musing from playing around with variations to Hilbert's tenth problem. A more direct question would be: Is every Diophantine set representable as some $S(f)$?

Answer by Gjergji Zaimi for Immersed surface with circle as a boundary

2013-01-09T01:00:31Z

Assuming your interest is in constant mean curvature surfaces with circular boundary, I found the survey, "Surfaces with constant mean curvature in Euclidean space" by R. Lopez to be a great introduction, and it contains the state of the art, and several references.

Hopf proved that the only constant mean curvature closed surfaces of genus 0 are spheres. Alexandrov's theorem says that constant mean curvature closed surfaces that are embedded are spheres. Unfortunately when we allow boundaries both analogs are conjectural:

Conjecture 1: The only constant mean curvature compact surfaces with circular boundary that are topological disks are spherical caps.

Conjecture 2: The only constant mean curvature compact surfaces with circular boundary that are embedded are spherical caps.

Answer by Gjergji Zaimi for A question on the Laurent phenomenon

2013-01-08T04:32:14Z

I would like to see a good answer to this question! What I write below is a collection ideas that I think are relevant.

Cluster algebras provide one way to generate non-trivial instances of the Laurent phenomenon, yet there seem to be many different kinds of recurrence relations which exhibit such magic, some of them highly nonlinear, such as $$x_{n+3}x_n^3x_{n-1}=x_{n+2}^3x_{n-1}^3-x_{n+2}^2x_{n+1}^3x_{n-2}+a(x_{n+1}x_n)^6.$$ Much of what I'm saying here comes from an article by A. Hone, "Laurent Polynomials and Superintegrable Maps". One can view a recurrence relation $$x_{n+k}=F(x_n,\dots,x_{n+k-1}) \mathrel{\mathop :}= F(\mathbf{x}_n),$$ as an iteration of the map $$\varphi:(x_0,\dots,x_{k-1})\to (x_1,\dots,x_{k-1},F(\mathbf{x}_0)),$$ and therefore as a discrete dynamical system, say over $\mathbb R^k$ or $\mathbb C^k$. It turns out that a lot of the combinatorial properties of the recurrent sequence are in agreement with the behavior of $\varphi$ as a discrete dynamical system.

I interpret the method that you sketch in your question about "linearising" using joint recurrences as a sort of analog of "separation of variables". Being able to use separation of variables is one of the characterizing properties of what people call integrable systems. Therefore it makes sense to look for an answer among the recurrences which give rise to discrete integrable systems (I understand there is a large literature on these).

From this perspective, it becomes evident that linearising using joint recurrences should have something to do with having "conserved quantities", i.e. expressions in the terms of the sequence that remain constant as the index varies.

With this in mind, let us look at the example of the Somos-4 sequence $$x_{n+4}x_{n}=\alpha x_{n+3}x_{n+1}+\beta x_{n+2}^2.$$ I believe the reference here is an earlier paper, "Integrality and the Laurent phenomenon for Somos 4 sequences", by C. Swart and A. Hone. Where they use the fact that the corresponding discrete dynamical system is integrable to conclude the Laurent phenomenon.

The expression $$T=\frac{x_{n-1}x_{n+2}}{x_nx_{n+1}}+\frac{\alpha x_n^2}{x_{n-1}x_{n+1}}+\frac{x_{n-2}x_{n+1}}{x_{n-1}x_n},$$ turns out to be independent of $n$. Denoting $\mathcal{I}=\alpha^2+\beta T$, the authors prove that, in fact, we have $x_n\in \mathbb Z[\alpha, \beta, \mathcal{I}, x_1^{\pm}, x_2,x_3,x_4]$.

This is done by introducing the sequence $w_n$ satisfying $w_1=1, w_2=-\sqrt{\alpha},w_3=-\beta,w_4=\mathcal{I}\sqrt{\alpha}$, as well as $$w_{2m+1}=w_m^3w_{m+2}-w_{m+1}^3w_{m-1} \quad, \quad w_{2m+2}=\frac{w_{m+2}^2w_{m+1}w_{m-1}-w_{m}^2w_{m+1}w_{m+3}}{\sqrt{\alpha}}.$$ Now the desired property follows from examining the recurrences $$x _{2m+1}=\frac{w _m ^2x_mx _{m+2}-w _{m+1}w _{m-1}x _{m+1} ^2}{x _1}$$ and $$x _{2m+2}=\frac{w _{m+2}w _{m-1}x _{m+1}x _{m+2}-w _mw _{m+1}x _m x _{m+3}}{\sqrt{\alpha}x_1}.$$

This kind of auxiliary recurrences might have not been what you had in mind, but I thought it might be relevant, and perhaps attract some expert's opinion. It would be great if the connection between discrete integrable systems and the Laurent phenomenon was better understood, and we could treat such results systematically.

Answer by Gjergji Zaimi for Integral transform and $\frac{1}{n!}$.

2012-12-18T16:23:56Z

Such a function would have to satisfy: $$\int(1-x)^2e^{v(x)}dx=-\frac12,$$ but the left hand side is clearly non-negative...

EDIT: Another contradiction for positive exponents is $$\int x(1-x)^4e^{v(x)}dx = -\frac{19}{120}$$

Infinite electrical networks and possible connections with LERW

2010-02-01T10:33:37Z

I've been exposed to various problems involving infinite circuits but never seen an extensive treatment on the subject. The main problem I am referring to is

Given a lattice L, we turn it into a circuit by placing a unit resistance in each edge. We would like to calculate the effective resistance between two points in the lattice (Or an asymptotic value for when the distance between the points gets large).

I know of an approach to solve the above introduced by Venezian, it involves superposition of potentials. An other approach I've heard of, involves lattice Green functions (I would like to read more about this). My first request is for a survey/article that treats these kind of problems (for the lattices $\mathbb{Z}^n$, Honeycomb, triangular etc.) and lists the main approaches/results in the field.

My second question (that is hopefully answered by the request above) is the following:

I noticed similarities in the transition probabilities of a Loop-erased random walk and the above mentioned effective resistances in $\mathbb{Z}^2$. Is there an actual relation between the two? (I apologize if this is obvious.)

Answer by Gjergji Zaimi for Reduction of $f$-solubility to $1$-factor

2012-11-26T02:49:58Z

Yes, this is a theorem that Tutte used to derive the f-factor theorem from the 1-factor theorem. He had already proved the f-factor theorem directly in 1952, in "The factors of graphs", MR0048775. The result you quote is from his paper from two years later, "A short proof of the factor theorem for finite graphs", MR0063008.

If you have trouble locating the reference, I can update this answer to give the actual argument, and construction of what you call $G_f$.

Answer by Gjergji Zaimi for series expansion of the q-Pochhammer symbol

2012-11-06T15:10:13Z

First notice that $$\sum _{n=1} ^{\infty} \frac{x^n}{n(1-x^{2n})} = \sum _{r=0} ^{\infty} \sum _{m=1} ^{\infty}\left(\frac{1}{2^r}\sum _{k|2m-1} \frac{1}{k}\right)x^{2^r(2m-1)}.$$ And similarly $$-\sum _{n=1}^{\infty}\frac{(-x)^n}{n(1-x^n)} = \sum _{s=1}^{\infty} \left(\sum _{k|s}\frac{(-1)^{k+1}}{k}\right)x^s.$$ So we need to show that the respective coefficients match, i.e.: $$\frac{1}{2^r}\sum _{k|2m-1} \frac{1}{k}=\sum _{k|s}\frac{(-1)^{k+1}}{k},$$ for $s=2^r(2m-1)$. But this is a simple corollary of $\frac{1}{2^r}=1-(\frac{1}{2}+\cdots+\frac{1}{2^r})$.

Answer by Gjergji Zaimi for Partitions into parts from an arithmetic progresion

2012-11-08T06:34:14Z

The answer is indeed affirmative, but was worked out before Grosswald's paper. The earliest paper I found which deals with a general version of this problem is

Roth, K.F., Szekeres, G. "Some asymptotic formulae in the theory of partitions", Quart. J. Math., Oxford Ser. (2) 5, (1954). 241–259, MR0067913

Suppose $\lbrace u_k\rbrace$ is an eventually increasing sequence of positive integers satisfying some mild technical conditions. The paper above gives accurate asymptotics for $p_u(n)$, the number of partitions of $n$ with distinct parts from $\lbrace u_k\rbrace$. The most relevant result is that for $n$ greater than some $n_0$ which depends on $\lbrace u_k\rbrace$ and $\delta$ we have a constant $c$ so that $$p_u(n+1)-p_u(n)\geq cn^{-\frac{s}{s+1}-\delta}p_u(n),$$ where $s=\lim_{k \to \infty}\frac{\log u_k}{\log k}$. In particular their result works for sequences $u_k=p(k)$ where $p$ is a polynomial taking integers to integers with $\gcd(p(1),p(2),\dots)=1$.

Length of Hirzebruch continued fractions

2012-11-02T22:16:40Z

Suppose $a,b$ are two natural numbers relatively prime to $n$ and to each other. Assume $n\geq ab+1$. Suppose further that $\frac{a}{b}\equiv k \pmod{n}$ for some $k\in \lbrace 1,2,\dots, n-1\rbrace$ and $\frac{a}{b}\equiv k'\pmod{n+ab}$ for some $k'\in \lbrace 1,2,\dots, n+ab-1\rbrace$.

Question: Is there an elementary proof that the length of the continued fraction of $\frac{n}{k}$ is equal to the length of the continued fraction of $\frac{n+ab}{k'}$?

This came out of a broader result, and for this particular case I can prove it using routine toric geometry, however I would like to know of some elementary tricks to deal with continued fractions.

Here by continued fraction I mean the Hirzebruch continued fraction $$\frac{n}{k}=a_0-\frac{1}{a_1-\frac{1}{a_2-\cdots}}.$$ For example, when $a=2, b=3$ and $n=17$, we get $k=12$ and $k'=16$, so the fractions are $$\frac{17}{12}=2-\frac{1}{2-\frac{1}{4-\frac{1}{2}}}\qquad and \qquad\frac{23}{16}=2-\frac{1}{2-\frac{1}{5-\frac{1}{2}}}.$$

Answer by Gjergji Zaimi for A special case of Catalan's conjecture

2012-11-06T07:12:00Z

Suppose the equation is $$y^p-z^r=1,$$ with $p,r$ odd primes. The classical approach to Catalan's conjecture was to consider two cases (similar to Fermat's last theorem) which go as follows:

First you rearrange the equation as $$(y-1)\left(\frac{y^p-1}{y-1}\right)=z^r$$ and then you consider the $\gcd$ of the factors on the left, it can only take the values $1$ or $p$. The first case $\gcd(y-1,\frac{y^p-1}{y-1})=1$ was shown to have no solutions by Cassels

J.W.S. Cassels, On the equation $a^x-b^y=1$, II, Proc. Cambridge Philos. Soc. 56 (1960), 97-103

with another proof given by S. Hyyro later. Cassels' proof uses elementary techniques. The punchline is that the second (hard) case is when $r| y$ and $p|z$.

Coming back to your equation we see that $2^p-1\equiv 1 \pmod{p}$, so we are in the first case, and you do not need the full strength of Mihăilescu's proof.

Answer by Gjergji Zaimi for Number of forests of size $i$ and the Tutte polynomial

2012-11-03T02:59:33Z

Here are two quick ways of proving this: (1) Notice that one of the many equivalent definitions of the Tutte polynomial says $$T_G(x,y)=\sum_{A\subset E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}$$ Where $A$ runs through subsets of the edges of $G$, and the function $k(A)$ measures the number of components of the graph $(V,A)$.

Here you only need consider the terms where $k(A)+|A|=|V|$, which happens precisely when $(A,V)$ is a forest!

(2) Remember that the Tutte polynomial satisfies the deletion-contraction relation $$T_{G}(x,y)=T_{G/e}(x,y)+T_{G-e}(x,y),$$ when $e$ is neither a loop nor a bridge. So you only need to show that the generating function of forests of a graph also satisfies this recurrence, as well as the "initial conditions" that it agrees with $t^{|E|-1}T_G(1+\frac{1}{t},1)$ for $G$ a tree.

Answer by Gjergji Zaimi for Irrationality measure of formal power series

2012-10-04T23:02:43Z

I think you will enjoy the paper "Irrationality of Power Series for Various Number Theoretic Functions", by W.D. Banks, F. Luca and I.E. Shparlinski. They use your $m_g$ as a measure of irrationality and give asymptotics on $m_g(f)$ for a variety of different power series $f$. They focus on power series with coefficients coming from arithmetic functions such as the Euler totient function, number of (prime, squarefree...) divisors, sum of divisors, Liouville function etc.

Answer by Gjergji Zaimi for Are two elements of a group determined up to simultaneous conjugacy by the conjugacy classes of all of their products?

2012-10-04T06:58:38Z

Suppose a group $G$ had the property that n-tuples $\lbrace x_1,\dots, x_n\rbrace$ and $\lbrace y_1,\dots,y_n\rbrace$ satisfy: if $w(x_1,\dots,x_n)$ is conjugate to $w(y_1,\dots,y_n)$ for all $w\in F_n$ then there is a uniform conjugator $g$ so that $y_i=gx_ig^{-1}$. Then as a corollary you get that if an endomorphism of $G$, satisfies $\varphi(x)$ is conjugate to $x$ for all $x$ then $\varphi$ is an inner automorphism.

However there are non-examples to this property in several classes of groups, including finite groups. The original property does however hold for torsion-free $\delta$-hyperbolic groups. This is proved in the paper "On endomorphisms of torsion-free hyperbolic groups", which also has references to the previous work.

Answer by Gjergji Zaimi for Hopf algebras and bijective antipodes

2012-09-28T15:39:11Z

It is conjectured that the antipode is bijective for all noetherian Hopf algebras (Skryabin), but no proof is known. Take a look at this recent short survey, "Noetherian Hopf Algebras", by K.R. Goodearl, where this is listed as conjecture 1.9. Skryabin's original paper is:

S. Skryabin, New results on the bijectivity of antipode of a Hopf algebra, J. Algebra 306 (2006), 622–633

Answer by Gjergji Zaimi for Chromatic number of the power set

2012-09-19T09:38:09Z

Your graph is going to be disconnected. Every connected component is a graph with vertices having finite symmetric difference with respect to some base set. Once you observe this, you can still use the parity argument, and split the sets according to whether they differ from the base set on an even or odd number of places.

Answer by Gjergji Zaimi for A generalization of Catalan numbers

2012-09-10T11:42:03Z

Yes, $(p,k)=(2,1)$ is the only case when the sequence is integral.

We always need $p\geq 2$. First let's pick a prime $q$ which is $\geq k$ and which divides one of the numbers in $\lbrace pk-1,pk-2,\dots,pk-k\rbrace$. This always exists for $k\geq 2$ by a famous result of Sylvester.

Now taking $n=q-k$, it is easy to check that $n+k$ does not divide $pn(pn-1)\cdots((p-1)n+1)$ and so $\frac{1}{n+k}\binom{pn}{n}$ is not an integer.

Does every polycube tiling imply a regular polycube tiling?

2012-04-06T22:53:39Z

Let's define d-polycubes to be a union of unit hypercubes from the $\mathbb Z^d$ tiling of d-dimensional Euclidean space which has connected interior. Given a tiling of $\mathbb R^d$ by identical copies of a d-polycube, we call this tiling regular if all the centers of the hypercubes have integer coordinates (i.e. the hypercubes fit together in a $\mathbb Z^d$ lattice).

I haven't been able to make much progress on the following seemingly simple and natural question:

If a given d-polycube tiles $\mathbb R^d$, must it also tile this space regularly?

I believe I have the $d=2$ case by a simple argument. As long as one has a connected tiled region with a concave boundary one can show that the adjacent 2-polycube (a.k.a. polyomino) at that corner must be placed to fit next to the squares of the already placed polyominoes so that edges meet edges and vertices meet vertices. We continue this until we tile the entire plane or we reach a convex region. Since the allowed angles are $\pi/2, \pi, 3\pi/2$ then we must have a rectangle. Now we can tile the space with translations of this rectangle.

However this doesn't work in $d\geq 3$ and I'm having trouble coming up with an argument in that case.

Answer by Gjergji Zaimi for In which geometries do triangles have a Euler-line ?

2012-09-09T21:01:15Z

In the paper "On some classical constructions extended to hyperbolic geometry", A. V. Akopyan proves an analogue of Feuerbach's theorem for hyperbolic geometry. Let $M_a,M_b,M_c$ be three points on sides of a triangle so that the corresponding cevians bisect the area of the triangle $ABC$. The intersection of these cevians, G, is the analogue of the centroid. Next if we take the circle passing through $M_a,M_b,M_c$, it will intersect each side a second time, in points $H_a,H_b,H_c$. The intersection of $AH_a,BH_b,CH_c$ is the analogue of the orthocenter, call it $H$.

The paper proves that there is a line passing through $G$, $H$, the circumcenter and the center of the circle passing through $M_a,M_b,M_c$. This is pretty much the most natural analogue for the Euler line in hyperbolic geometry.

Answer by Gjergji Zaimi for Coloring tensor products of graphs

2012-09-03T14:04:55Z

The only way that two vertices $(u,v)$ and $(u',v')$ end up getting the same color is if $f(u)=f(u')$. But then there is no edge between $u$ and $u'$ in $G$ so there is no edge between $(u,v)$ and $(u',v')$ in $G\times H$. So your conjecture is true for all graphs.

In fact, as explained in the page you linked to above, a coloring with $n$ colors is simply a graph homomorphism to $K_n$, the complete graph on $n$ vertices. Since we have a homomorphism $G\times H\to G$ we can simply compose this with a homomorphism $G\to K_n$ whenever $\chi(G)=n$. This gives your construction. It also proves that $\chi(G\times H)\le \min{\chi(G),\chi(H)}$.

Answer by Gjergji Zaimi for inversion vector for multiset permutation

2012-08-01T08:51:49Z

One can define the inversion vector in the same way and the same proof goes through. Given a multiset $M$ and a multipermutation $\pi=\pi_1\cdots \pi_n$, define its inversion vector to be $i(\pi)=(i_1,i_2,\dots,i_n)$, where $$i_k=\left|\lbrace j \text{ such that } j>k \text{ and } \pi_{k}>\pi_j\rbrace\right|.$$ (notice the strict inequalities)

Theorem: Given $i(\pi)$, we can recover $\pi$.

Proof: Suppose we have determined $\pi_1,\pi_2,\dots, \pi_{k-1}$. Let $M'=M/\lbrace \pi_1,\dots, \pi_{k-1}\rbrace$. We know from $i_{k}$ the number of indices $j$ so that $k+1\le j\le n$ and $\pi_j<\pi_{k}$. So $\pi_{k}$ is greater than exactly $i_k$ elements of $M'$, and is therefore uniquely determined.

Notice that if your multiset is $\lbrace 1^{m_1},\dots,r^{m_r}\rbrace$, then any inversion vector still satisfies $i_k\le n-k$. But clearly not all such vectors can be achieved as the inversion vector of a permutation of $M$. Now, if one tries to write a generating function of inversion vectors, i.e. $\sum_{M} x_1^{i_1}\cdots x_n^{i_n}$ then this won't factor into $\prod P_i(x_i)$ for a general multiset. For example, if $M=\lbrace 1,1,2 \rbrace$ the generating function is $1+x_2+x_1x_2$. This implies that there cannot be a "natural" radix representation to encode these inversion vectors.

All in all, Patricia's comment gives a much quicker way to get around this problem. Just pretend your multiset is actually a set, by giving it a natural total order and then write the permutations as permutations in this new set (this is called the standard permutation corresponding to the multiset permutation).

Comment by Gjergji Zaimi

2013-05-15T22:35:45Z

Yes, that's the theorem I was referring to.

Comment by Gjergji Zaimi

2013-05-07T02:07:35Z

Oops! Thanks Vladimir!

Comment by Gjergji Zaimi

2013-04-25T05:43:25Z

See Igor's answer for an argument along the lines you want. mathoverflow.net/questions/27508/…

Comment by Gjergji Zaimi

2013-04-23T23:19:45Z

@Samuele, if you want a definition of flexible algebras that doesn't have several occurrences of a variable in the same monomial, notice that an algebra is flexible iff $(x,y,z)+(z,y,x)=0$. The parenthesis denote associators.

Comment by Gjergji Zaimi

2013-04-19T12:53:51Z

There is already a very nice article in the monthly about this :) jstor.org/stable/27641834

Comment by Gjergji Zaimi

2013-03-19T03:25:59Z

What do you consider closed form here? A MacMahon type product? A generating function for plane partitions? Something else?...

Comment by Gjergji Zaimi

2013-03-12T16:55:33Z

Marc, are you asking for motivation for my question or Malliavin's theorem?

Comment by Gjergji Zaimi

2013-03-08T18:45:56Z

Thanks quid! The tag suggestion doesn't work for me, for some reason, and I tagged it by mistake.

Comment by Gjergji Zaimi

2013-03-06T14:41:04Z

mathoverflow.net/questions/76134/…

Comment by Gjergji Zaimi

2013-03-04T19:07:10Z

Is this homework?

Comment by Gjergji Zaimi

2013-03-03T13:46:18Z

@Amit, on the contrary, such examples all follow from Newton polytope considerations. If the Newton polytope is not decomposable as a Minkowski sum, then such an $m$ does not exist.

Comment by Gjergji Zaimi

2013-02-28T07:41:27Z

But now you know who to ask :)

Comment by Gjergji Zaimi

2013-02-28T07:39:58Z

Coincidentally I was recently reading a paper of A. Sikora, where he mentions that $sl_2$ character varieties aren't always reduced as schemes. See section 12 in arxiv.org/abs/0902.2589 However, for the 3-manifold group case, he cites work of M.Kapovich that doesn't seem to be in print.

Comment by Gjergji Zaimi

2013-02-21T03:17:41Z

From someone who didn't do that well at IMO, still, the problems on gazeta matematica are a lot of fun!

Comment by Gjergji Zaimi

2013-02-13T03:59:49Z

Look at chapter 1 in Macdonald's book on symmetric functions. Though, that identity is very close to the definition of the elementary symmetric polynomials :)