User gjergji zaimi - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T22:16:11Z http://mathoverflow.net/feeds/user/2384 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130357/trying-to-solve-show-that-n-does-not-divide-3n-2n-for-n-greater-than-or-equa/130362#130362 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. Gjergji Zaimi 2013-05-11T19:46:32Z 2013-05-11T19:46:32Z <p>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.</p> http://mathoverflow.net/questions/129914/can-a-harmonic-number-be-a-rational-number-for-non-integer-rational-argument/129916#129916 Answer by Gjergji Zaimi for Can a harmonic number be a rational number for non-integer rational argument? Gjergji Zaimi 2013-05-07T01:19:07Z 2013-05-07T02:07:10Z <p>The answer is "no". Your function $H_z$ which is the same as $\psi(z+1)+\gamma$, where $\psi$ is the <a href="http://en.wikipedia.org/wiki/Digamma_function" rel="nofollow">digamma function</a>, 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, <a href="http://www.sciencedirect.com/science/article/pii/S0022314X06002927" rel="nofollow">"Transcendental values of the digamma function"</a>.</p> <p>Notice that at rational values the digamma function has an explicit evaluation given by <a href="http://en.wikipedia.org/wiki/Digamma_function#Gauss.27s_digamma_theorem" rel="nofollow">Gauss's formula</a>.</p> http://mathoverflow.net/questions/58040/groups-quantum-groups-and-fill-in-the-blank Groups, quantum groups and (fill in the blank) Gjergji Zaimi 2011-03-10T05:50:10Z 2013-05-06T22:09:26Z <p>In the study of special functions there are three levels of objects, classical, basic and elliptic. These correspond to <a href="http://en.wikipedia.org/wiki/Generalized_hypergeometric_function" rel="nofollow">classical hypergeometric functions</a>, <a href="http://en.wikipedia.org/wiki/Basic_hypergeometric_series" rel="nofollow">basic (q-) hypergeometric functions</a>, and <a href="http://en.wikipedia.org/wiki/Elliptic_hypergeometric_series" rel="nofollow">elliptic hypergeometric functions</a>.</p> <p>In combinatorics these notions are related to enumeration, q-enumeration and "elliptic enumeration" (see <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WHS-4KPX8NP-1&amp;_user=10&amp;_coverDate=04%2F30%2F2007&amp;_rdoc=1&amp;_fmt=high&amp;_orig=gateway&amp;_origin=gateway&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1672599468&amp;_rerunOrigin=google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=5128d66dcddee96b22bceb59d583e99a&amp;searchtype=a" rel="nofollow">this</a> article of Schlosser).</p> <p>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?</p> http://mathoverflow.net/questions/128747/formalization-and-background-of-a-formula-concering-the-integral-points-of-a-p/129493#129493 Answer by Gjergji Zaimi for Formalization (and background) of a formula, concering the integral points of a polygon. Gjergji Zaimi 2013-05-03T06:06:37Z 2013-05-03T06:06:37Z <p>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.</p> <p>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.</p> <p>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. </p> <p>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.</p> <p>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.</p> <p>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. :)</p> http://mathoverflow.net/questions/128249/estimate-on-sum-of-squares-of-multinomial-coefficients/128418#128418 Answer by Gjergji Zaimi for Estimate on sum of squares of multinomial coefficients Gjergji Zaimi 2013-04-23T00:46:44Z 2013-04-23T00:46:44Z <p>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 <a href="http://arxiv.org/abs/0807.5028" rel="nofollow">"Counting Abelian squares"</a>, 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.</p> <p>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}).$$</p> http://mathoverflow.net/questions/124005/a-possible-refinement-of-a-theorem-of-malliavin A possible refinement of a theorem of Malliavin Gjergji Zaimi 2013-03-08T18:21:16Z 2013-03-11T23:28:40Z <p>Due to a theorem of Malliavin (an improvement of an erlier theorem of Dixmier and Malliavin, see <a href="http://www.math.ubc.ca/~cass/research/pdf/Dixmier-Malliavin.pdf" rel="nofollow">here</a>) 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.</p> <p><strong>Question:</strong> Is it known whether we can choose the $u_i,v_i$ to vary continuously with $f$?</p> <p>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 <a href="http://www.math.columbia.edu/~ums/pdf/alexthesis.pdf" rel="nofollow">this undergraduate thesis</a>.</p> <p>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.</p> http://mathoverflow.net/questions/123179/access-to-a-preprint-by-d-n-verma/123215#123215 Answer by Gjergji Zaimi for Access to a preprint by D. N. Verma Gjergji Zaimi 2013-02-28T13:44:11Z 2013-02-28T13:44:11Z <p>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,...$. </p> <p>See section 2.11 in the paper <a href="http://math.stanford.edu/~vakil/files/HMSV2aug1206.pdf" rel="nofollow">"The moduli space of n points on the line is cut out by simple quadrics when n is not six"</a>, 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 <a href="http://arxiv.org/abs/1211.3941" rel="nofollow">"The ring of evenly weighted points on the line"</a>, by M. Hering, B. Howard. Hope this helps.</p> http://mathoverflow.net/questions/121745/principal-specialization-of-projective-schur-functions/121782#121782 Answer by Gjergji Zaimi for principal specialization of projective Schur functions Gjergji Zaimi 2013-02-14T09:33:10Z 2013-02-15T15:32:18Z <p>There is a very nice specialization when you consider <em>infinitely many</em> 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 &lt; j \le m} \frac{q^{\lambda_j}-q^{\lambda_i}}{1-q^{\lambda_i+\lambda_j}}$$ where $\lambda$ is a partition of length $m$.</p> <p>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$.</p> <p>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, <a href="http://arxiv.org/abs/math/0603086" rel="nofollow">"Schur Q-polynomials, multiple hypergeometric series and enumeration of marked shifted tableaux"</a>, you should have what you want. Combinatorially this is interesting because it gives the $q$-enumeration of marked shifted tableaux.</p> http://mathoverflow.net/questions/87293/on-a-remark-of-tait-on-flt-for-the-exponent-3 On a remark of Tait on FLT for the exponent 3 Gjergji Zaimi 2012-02-01T23:36:07Z 2013-02-13T19:37:07Z <p>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:</p> <blockquote> <p>In the <em>Proceedings of the Royal Society of Edinburgh</em>, vol.7, p.144, in some mathematical notes by professor P.G. Tait, it is stated:</p> <p>"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$.</p> <p>This furnishes an easy proof of the impossibility of finding two integers the sum of whose cubes is a cube."</p> <p>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.</p> </blockquote> <p>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?</p> http://mathoverflow.net/questions/121660/a-known-pythagorean-identity-in-algebra/121668#121668 Answer by Gjergji Zaimi for A "known" Pythagorean identity in algebra? Gjergji Zaimi 2013-02-13T01:32:40Z 2013-02-13T01:32:40Z <p>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).$$</p> <p>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$$</p> http://mathoverflow.net/questions/120172/sets-of-integers-represented-by-degree-zero-rational-functions Sets of integers represented by degree zero rational functions Gjergji Zaimi 2013-01-29T02:54:13Z 2013-01-29T08:31:03Z <p>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.</p> <p>Which sets $S\subset \mathbb Z$ can be written as $S(f)$ for some $f$ as above?</p> <p>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$. </p> <p>This question is just a musing from playing around with variations to <a href="http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem" rel="nofollow">Hilbert's tenth problem</a>. A more direct question would be: Is every <a href="http://en.wikipedia.org/wiki/Diophantine_set" rel="nofollow">Diophantine set</a> representable as some $S(f)$?</p> http://mathoverflow.net/questions/118405/immersed-surface-with-circle-as-a-boundary/118413#118413 Answer by Gjergji Zaimi for Immersed surface with circle as a boundary Gjergji Zaimi 2013-01-09T01:00:31Z 2013-01-09T01:00:31Z <p>Assuming your interest is in constant mean curvature surfaces with circular boundary, I found the survey, <a href="http://www.ugr.es/~rcamino/publications/pdf/art57.pdf" rel="nofollow">"Surfaces with constant mean curvature in Euclidean space"</a> by R. Lopez to be a great introduction, and it contains the state of the art, and several references. </p> <p>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:</p> <blockquote> <p><strong>Conjecture 1:</strong> The only constant mean curvature compact surfaces with circular boundary that are topological disks are spherical caps.</p> <p><strong>Conjecture 2:</strong> The only constant mean curvature compact surfaces with circular boundary that are embedded are spherical caps.</p> </blockquote> http://mathoverflow.net/questions/118157/a-question-on-the-laurent-phenomenon/118332#118332 Answer by Gjergji Zaimi for A question on the Laurent phenomenon Gjergji Zaimi 2013-01-08T04:32:14Z 2013-01-08T04:32:14Z <p>I would like to see a good answer to this question! What I write below is a collection ideas that I think are relevant.</p> <p>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, <a href="http://arxiv.org/abs/math.NT/0702280" rel="nofollow">"Laurent Polynomials and Superintegrable Maps"</a>. 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.</p> <p>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 <em>discrete integrable systems</em> (I understand there is a large literature on these). </p> <p>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.</p> <p>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, <a href="http://arxiv.org/abs/math/0508094" rel="nofollow">"Integrality and the Laurent phenomenon for Somos 4 sequences"</a>, by C. Swart and A. Hone. Where they use the fact that the corresponding discrete dynamical system is integrable to conclude the Laurent phenomenon.</p> <p>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]$.</p> <p>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}.$$</p> <p>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.</p> http://mathoverflow.net/questions/116712/integral-transform-and-frac1n/116721#116721 Answer by Gjergji Zaimi for Integral transform and $\frac{1}{n!}$. Gjergji Zaimi 2012-12-18T16:23:56Z 2012-12-18T16:45:36Z <p>Such a function would have to satisfy: $$\int(1-x)^2e^{v(x)}dx=-\frac12,$$ but the left hand side is clearly non-negative...</p> <p>EDIT: Another contradiction for positive exponents is $$\int x(1-x)^4e^{v(x)}dx = -\frac{19}{120}$$</p> http://mathoverflow.net/questions/13649/infinite-electrical-networks-and-possible-connections-with-lerw Infinite electrical networks and possible connections with LERW Gjergji Zaimi 2010-02-01T10:33:37Z 2012-12-17T18:30:51Z <p>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</p> <blockquote> <p>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). </p> </blockquote> <p>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.</p> <p>My second question (that is hopefully answered by the request above) is the following:</p> <p>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.)</p> http://mathoverflow.net/questions/114470/reduction-of-f-solubility-to-1-factor/114480#114480 Answer by Gjergji Zaimi for Reduction of $f$-solubility to $1$-factor Gjergji Zaimi 2012-11-26T02:49:58Z 2012-11-26T02:49:58Z <p>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", <a href="http://www.ams.org/mathscinet-getitem?mr=48775" rel="nofollow">MR0048775</a>. The result you quote is from his paper from two years later, "A short proof of the factor theorem for finite graphs", <a href="http://www.ams.org/mathscinet-getitem?mr=63008" rel="nofollow">MR0063008</a>. </p> <p>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$.</p> http://mathoverflow.net/questions/111648/series-expansion-of-the-q-pochhammer-symbol/111651#111651 Answer by Gjergji Zaimi for series expansion of the q-Pochhammer symbol Gjergji Zaimi 2012-11-06T15:10:13Z 2012-11-20T01:50:43Z <p>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})$.</p> http://mathoverflow.net/questions/111507/partitions-into-parts-from-an-arithmetic-progresion/111785#111785 Answer by Gjergji Zaimi for Partitions into parts from an arithmetic progresion Gjergji Zaimi 2012-11-08T06:34:14Z 2012-11-08T06:34:14Z <p>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</p> <blockquote> <p>Roth, K.F., Szekeres, G. "Some asymptotic formulae in the theory of partitions", Quart. J. Math., Oxford Ser. (2) 5, (1954). 241–259, <a href="http://www.ams.org/mathscinet-getitem?mr=67913" rel="nofollow">MR0067913</a></p> </blockquote> <p>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 <em>distinct parts</em> 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$.</p> http://mathoverflow.net/questions/111312/length-of-hirzebruch-continued-fractions Length of Hirzebruch continued fractions Gjergji Zaimi 2012-11-02T22:16:40Z 2012-11-07T08:17:06Z <p>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$.</p> <blockquote> <p><strong>Question:</strong> 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'}$?</p> </blockquote> <p>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. </p> <hr> <p>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}}}.$$</p> http://mathoverflow.net/questions/111617/a-special-case-of-catalans-conjecture/111624#111624 Answer by Gjergji Zaimi for A special case of Catalan's conjecture Gjergji Zaimi 2012-11-06T07:12:00Z 2012-11-06T07:35:26Z <p>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:</p> <p>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</p> <blockquote> <p>J.W.S. Cassels, On the equation $a^x-b^y=1$, II, Proc. Cambridge Philos. Soc. 56 (1960), 97-103</p> </blockquote> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/111326/number-of-forests-of-size-i-and-the-tutte-polynomial/111337#111337 Answer by Gjergji Zaimi for Number of forests of size $i$ and the Tutte polynomial Gjergji Zaimi 2012-11-03T02:59:33Z 2012-11-03T02:59:33Z <p>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)$.</p> <p>Here you only need consider the terms where $k(A)+|A|=|V|$, which happens precisely when $(A,V)$ is a forest!</p> <p>(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.</p> http://mathoverflow.net/questions/108864/irrationality-measure-of-formal-power-series/108870#108870 Answer by Gjergji Zaimi for Irrationality measure of formal power series Gjergji Zaimi 2012-10-04T23:02:43Z 2012-10-04T23:10:36Z <p>I think you will enjoy the paper <a href="http://www.springerlink.com/content/j534776137785108/" rel="nofollow">"Irrationality of Power Series for Various Number Theoretic Functions"</a>, 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.</p> http://mathoverflow.net/questions/108783/are-two-elements-of-a-group-determined-up-to-simultaneous-conjugacy-by-the-conjug/108787#108787 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? Gjergji Zaimi 2012-10-04T06:58:38Z 2012-10-04T06:58:38Z <p>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.</p> <p>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 <a href="http://arxiv.org/abs/0903.2306" rel="nofollow">"On endomorphisms of torsion-free hyperbolic groups"</a>, which also has references to the previous work.</p> http://mathoverflow.net/questions/108352/hopf-algebras-and-bijective-antipodes/108356#108356 Answer by Gjergji Zaimi for Hopf algebras and bijective antipodes Gjergji Zaimi 2012-09-28T15:39:11Z 2012-09-28T15:39:11Z <p>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, <a href="http://arxiv.org/abs/1201.4854" rel="nofollow">"Noetherian Hopf Algebras"</a>, by K.R. Goodearl, where this is listed as conjecture 1.9. Skryabin's original paper is:</p> <blockquote> <p>S. Skryabin, <a href="http://www.sciencedirect.com/science/article/pii/S0021869306002328" rel="nofollow">New results on the bijectivity of antipode of a Hopf algebra</a>, J. Algebra 306 (2006), 622–633</p> </blockquote> http://mathoverflow.net/questions/107540/chromatic-number-of-the-power-set/107544#107544 Answer by Gjergji Zaimi for Chromatic number of the power set Gjergji Zaimi 2012-09-19T09:38:09Z 2012-09-19T09:38:09Z <p>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. </p> http://mathoverflow.net/questions/106804/a-generalization-of-catalan-numbers/106806#106806 Answer by Gjergji Zaimi for A generalization of Catalan numbers Gjergji Zaimi 2012-09-10T11:42:03Z 2012-09-10T21:12:09Z <p>Yes, $(p,k)=(2,1)$ is the only case when the sequence is integral.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/93365/does-every-polycube-tiling-imply-a-regular-polycube-tiling Does every polycube tiling imply a regular polycube tiling? Gjergji Zaimi 2012-04-06T22:53:39Z 2012-09-09T23:18:35Z <p>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 <em>regular</em> if all the centers of the hypercubes have integer coordinates (i.e. the hypercubes fit together in a $\mathbb Z^d$ lattice).</p> <p>I haven't been able to make much progress on the following seemingly simple and natural question:</p> <blockquote> <p>If a given d-polycube tiles $\mathbb R^d$, must it also tile this space regularly?</p> </blockquote> <p>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.</p> <p>However this doesn't work in $d\geq 3$ and I'm having trouble coming up with an argument in that case.</p> http://mathoverflow.net/questions/106714/in-which-geometries-do-triangles-have-a-euler-line/106753#106753 Answer by Gjergji Zaimi for In which geometries do triangles have a Euler-line ? Gjergji Zaimi 2012-09-09T21:01:15Z 2012-09-09T21:01:15Z <p>In the paper <a href="http://arxiv.org/abs/1105.2153" rel="nofollow">"On some classical constructions extended to hyperbolic geometry"</a>, 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$. </p> <p>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.</p> http://mathoverflow.net/questions/106243/coloring-tensor-products-of-graphs/106247#106247 Answer by Gjergji Zaimi for Coloring tensor products of graphs Gjergji Zaimi 2012-09-03T14:04:55Z 2012-09-03T14:04:55Z <p>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.</p> <p>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)}$.</p> http://mathoverflow.net/questions/103664/inversion-vector-for-multiset-permutation/103670#103670 Answer by Gjergji Zaimi for inversion vector for multiset permutation Gjergji Zaimi 2012-08-01T08:51:49Z 2012-08-02T02:21:18Z <p>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)</p> <p><strong>Theorem:</strong> Given $i(\pi)$, we can recover $\pi$. </p> <p><em>Proof:</em> 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&lt;\pi_{k}$. So $\pi_{k}$ is greater than exactly $i_k$ elements of $M'$, and is therefore uniquely determined.</p> <hr> <p>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. </p> <p>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).</p> http://mathoverflow.net/questions/128747/formalization-and-background-of-a-formula-concering-the-integral-points-of-a-p/129493#129493 Comment by Gjergji Zaimi Gjergji Zaimi 2013-05-15T22:35:45Z 2013-05-15T22:35:45Z Yes, that's the theorem I was referring to. http://mathoverflow.net/questions/129914/can-a-harmonic-number-be-a-rational-number-for-non-integer-rational-argument/129916#129916 Comment by Gjergji Zaimi Gjergji Zaimi 2013-05-07T02:07:35Z 2013-05-07T02:07:35Z Oops! Thanks Vladimir! http://mathoverflow.net/questions/128681/a-divergent-series-related-to-the-number-of-divisors-of-of-p-1 Comment by Gjergji Zaimi Gjergji Zaimi 2013-04-25T05:43:25Z 2013-04-25T05:43:25Z See Igor's answer for an argument along the lines you want. <a href="http://mathoverflow.net/questions/27508/factors-of-p-1-when-p-is-prime" rel="nofollow" title="factors of p 1 when p is prime">mathoverflow.net/questions/27508/&hellip;</a> http://mathoverflow.net/questions/128547/what-is-flexible-about-flexible-algebras Comment by Gjergji Zaimi Gjergji Zaimi 2013-04-23T23:19:45Z 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. http://mathoverflow.net/questions/128079/a-bit-of-primes Comment by Gjergji Zaimi Gjergji Zaimi 2013-04-19T12:53:51Z 2013-04-19T12:53:51Z There is already a very nice article in the monthly about this :) <a href="http://www.jstor.org/stable/27641834" rel="nofollow">jstor.org/stable/27641834</a> http://mathoverflow.net/questions/124923/evaluating-an-infinite-product-of-q-exponentials Comment by Gjergji Zaimi Gjergji Zaimi 2013-03-19T03:25:59Z 2013-03-19T03:25:59Z What do you consider closed form here? A MacMahon type product? A generating function for plane partitions? Something else?... http://mathoverflow.net/questions/124005/a-possible-refinement-of-a-theorem-of-malliavin Comment by Gjergji Zaimi Gjergji Zaimi 2013-03-12T16:55:33Z 2013-03-12T16:55:33Z Marc, are you asking for motivation for my question or Malliavin's theorem? http://mathoverflow.net/questions/124005/a-possible-refinement-of-a-theorem-of-malliavin Comment by Gjergji Zaimi Gjergji Zaimi 2013-03-08T18:45:56Z 2013-03-08T18:45:56Z Thanks quid! The tag suggestion doesn't work for me, for some reason, and I tagged it by mistake. http://mathoverflow.net/questions/123760/topological-characterization-of-the-closed-interval-0-1 Comment by Gjergji Zaimi Gjergji Zaimi 2013-03-06T14:41:04Z 2013-03-06T14:41:04Z <a href="http://mathoverflow.net/questions/76134/topological-characterisation-of-the-real-line" rel="nofollow" title="topological characterisation of the real line">mathoverflow.net/questions/76134/&hellip;</a> http://mathoverflow.net/questions/123561/number-of-matchings-in-regular-bipartite-graph Comment by Gjergji Zaimi Gjergji Zaimi 2013-03-04T19:07:10Z 2013-03-04T19:07:10Z Is this homework? http://mathoverflow.net/questions/123459/when-adding-a-constant-makes-a-multivariate-polynomial-reducible Comment by Gjergji Zaimi Gjergji Zaimi 2013-03-03T13:46:18Z 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. http://mathoverflow.net/questions/123198/can-the-sl-2-character-variety-of-a-three-manifold-be-nonreduced Comment by Gjergji Zaimi Gjergji Zaimi 2013-02-28T07:41:27Z 2013-02-28T07:41:27Z But now you know who to ask :) http://mathoverflow.net/questions/123198/can-the-sl-2-character-variety-of-a-three-manifold-be-nonreduced Comment by Gjergji Zaimi Gjergji Zaimi 2013-02-28T07:39:58Z 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 <a href="http://arxiv.org/abs/0902.2589" rel="nofollow">arxiv.org/abs/0902.2589</a> However, for the 3-manifold group case, he cites work of M.Kapovich that doesn't seem to be in print. http://mathoverflow.net/questions/10146/good-books-on-problem-solving-math-olympiad/122494#122494 Comment by Gjergji Zaimi Gjergji Zaimi 2013-02-21T03:17:41Z 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! http://mathoverflow.net/questions/121660/a-known-pythagorean-identity-in-algebra/121668#121668 Comment by Gjergji Zaimi Gjergji Zaimi 2013-02-13T03:59:49Z 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 :)