User felix - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T08:47:36Z http://mathoverflow.net/feeds/user/7001 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92683/finiteness-conditions-and-veronese-subrings/93001#93001 Answer by felix for Finiteness conditions and Veronese subrings felix 2012-04-03T14:05:02Z 2012-04-03T14:05:02Z <p>In case $G$ is finite, this cannot happen.</p> <p>(This might extend to the general case of finitely generated groups, as Fred told me when we talked about this in my office :-) )</p> <hr> <p>First, let me show that $R$ is of finite type over $R_0$ in case $R_0$ is noetherian and $G$ is finite. For that, it suffices to show that every $R_g$, $g \in G$ is finitely generated as an $R_0$-module.</p> <p>Now fix some $g \in G$. In case $R_g = { 0 }$, we are done. Otherwise, let $\alpha \in R_g \setminus { 0 }$. As $G$ is a finite group, there exists some $n > 0$ such that $n g = 0$. As $R$ is integral, $\beta := \alpha^{n-1} \neq 0$ is a non-trivial element of $R_{g^{-1}}$.</p> <p>Now the map $\varphi : R_g \to R_0$, $x \mapsto \beta x$ is an injective $R_0$-module homomorphism. The image, $\beta R_g$, is therefore isomorphic to $R_g$ as an $R_0$-module. As $R_0$ is noetherian, every $R_0$-submodule of $R_0$ is finitely generated, whence $\beta R_g$ and thus $R_g$ is a finitely generated $R_0$-module.</p> <p>This shows that $R$ is of finite type over $R_0$.</p> <hr> <p>Now let me go back to the original problem. As $R_0$ is a subring of both $R$ and $R_{(H)}$, it is of finite type over the noetherian ring $A$. Therefore, $R_0$ is noetherian as well. So in case $G$ is finite, the above shows that $R$ is of finite type over $R_0$, and thus also over $A$.</p> http://mathoverflow.net/questions/85480/is-there-an-analogue-of-finite-fields-for-products-of-two-prime-powers/85671#85671 Answer by felix for Is there an analogue of finite fields for products of two prime powers? felix 2012-01-14T15:50:06Z 2012-01-14T15:50:06Z <p>A natural number $n$ is the product of precisely two prime powers if and only if there exists an abelian group of order $n$ having precisely two maximal subgroups. (And that group is unique up to isomorphism.)</p> http://mathoverflow.net/questions/60894/a-pair-of-subset-of-natural-numbers-having-density-but-whose-intersection-has-no/60898#60898 Answer by felix for A pair of subset of natural numbers having density, but whose intersection has no density felix 2011-04-07T07:25:06Z 2011-04-07T07:25:06Z <p>Take $A$ the set of even numbers, $B$ the set of odd numbers. Than $d(A) = d(B) = \frac{1}{2}$, while $d(A \cap B) = 0$ since $A \cap B = \emptyset$.</p> http://mathoverflow.net/questions/57084/a-unique-zero-of-a-system-of-polynomials-is-a-zero-of-a-finite-system/57088#57088 Answer by felix for A unique zero of a system of polynomials is a zero of a finite system. felix 2011-03-02T08:14:02Z 2011-03-02T08:14:02Z <p>The existence of a finite $S_2$ follows from <a href="http://en.wikipedia.org/wiki/Hilbert%27s_basis_theorem" rel="nofollow">Hilbert's basis theorem</a>, as $\mathbb{R}$ is obviously Noetherian. Just take a finite generating system of the ideal generated by $S$.</p> <p>About your auxilliary questions: a) This is wrong. Just take $f = x^2 + y^2$; then ${ f }$ has the unique zero $(0, 0)$ in $\mathbb{R}^2$, while it has no isolated zero in $\mathbb{C}^2$.</p> <p>b) The ideal generated by $S$ is finitely generated. The set $S$ itself does not needs to have any algebraic structure, unless you take the set of <i>all</i> polynomials which vanish in $p$ (then it is a maximal ideal in $\mathbb{R}[x_1, \dots, x_n]$). In any case, replacing $S$ by the ideal generated by $S$ does not change the zero set (<a href="http://en.wikipedia.org/wiki/Algebraic_variety" rel="nofollow">variety</a>) of $S$.</p> http://mathoverflow.net/questions/41716/how-random-are-unit-lattices-in-number-fields How random are unit lattices in number fields? felix 2010-10-10T22:28:35Z 2011-02-21T20:53:05Z <p>I was wondering how random unit lattices in number fields are. To make this more precise:</p> <p>If $K$ is a number field with embeddings $\sigma_1, \dots, \sigma_n, \overline{\sigma_{r+1}}, \dots, \overline{\sigma_n} \to \mathbb{C}$ (so we have $r$ real embeddings and $2 (n - r)$ complex embeddings), let $\mathcal{O}_K$ be the ring of integers and $\Lambda_K := \{ (\log |\sigma_1(\varepsilon)|^{d_1}, \dots, \log |\sigma_n(\varepsilon)|^{d_n}) \mid \varepsilon \in \mathcal{O}_K^\ast \}$ be the unit lattice, where $d_i = 1$ if $\sigma_i(K) \subseteq \mathbb{R}$ and $d_i = 2$ otherwise.</p> <p>Then $\Lambda_K$ is always contained in $H := \{ (x_1, \dots, x_n) \in \mathbb{R}^n \mid \sum_{i=1}^n x_i = 0 \}$, and $\det \Lambda_K$ is the regulator $R_K$ of $K$. Let us normalize $\Lambda_K$ by $\hat{\Lambda}_K := \frac{1}{\sqrt[n]{R_K}} \Lambda_K$; then $\det \hat{\Lambda}_K = 1$.</p> <p>Now my question is: can we say something on how random the lattices $\hat{\Lambda}_K$ are among all lattices in $H$ of determinant 1? (For example, for fixed signature $(r, n-r)$ of $K$.)</p> <p>Since these lattices are not completely random (they consist of vectors of logarithms of algebraic numbers), it is maybe better to ask something like this:</p> <ul> <li><p>Given $\varepsilon > 0$ and a lattice $\Lambda \subseteq H$ with determinant 1, does there exists a number field $K$ of signature $(r, n - r)$ such that there is a basis $(v_i)_i$ of $\hat{\Lambda}_K$ and a basis $(w_i)_i$ of $\Lambda$ such that $\|v_i - w_i\| &lt; \varepsilon$ for all $i$?</p></li> <li><p>And if this exists, can one bound the discriminant of $K$ (or any other invariant of $K$) in terms of $\varepsilon$?</p></li> </ul> <p>(Of course, this question is only interesting when $n > 2$.)</p> <p>I assume that this is a very hard problem, so I'd be happy about any hint on whether something about this is known, whether someone is working on this, how one could proof such things, etc.</p> http://mathoverflow.net/questions/48251/methods-for-solving-pells-equation/48252#48252 Answer by felix for Methods for solving Pell's equation? felix 2010-12-04T05:55:27Z 2010-12-04T05:55:27Z <p>Any algorithm for computing fundamental units of a real quadratic number field $\mathbb{Q}(\sqrt{D})$ can be used for solving Pell's equation. (You might have to do a bit of work to convert the result, but that can be done in polynomial time...)</p> <p>See for example M. Jacobson, H. Williams: Solving the Pell Equation. Springer, 2009.</p> http://mathoverflow.net/questions/37325/what-is-the-link-between-sections-and-sections-schemes/39582#39582 Answer by felix for What is the link between sections and sections? (schemes) felix 2010-09-22T07:18:06Z 2010-09-22T07:18:06Z <p>Sections to the morphism $X \to S$ are more or less $S$-rational points of $X$: if for example $S = Spec(R)$ and $X = Spec(R[x_1, \dots, x_n]/(f_1, \dots, f_m))$ with polynomials $f_1, \dots, f_m \in R[x_1, \dots, x_n]$, then sections to $X \to S$ correspond to points $(a_1, \dots, a_n) \in R^n$ with $f_i(a_1, \dots, a_n) = 0$ for all $i$.</p> <p>On the other hand, the elements of $\mathcal{O}_X(U)$ can be seen as holomorphic functions on $U$.</p> <p>So the one kind of sections can be seen as "points" of the geometric object, the others can be seen as "functions" on the geometric object.</p> http://mathoverflow.net/questions/37563/other-norms-for-lattice-reduction-techniques-lll-pslq/37586#37586 Answer by felix for Other norms for Lattice reduction techniques (LLL, PSLQ)? felix 2010-09-03T08:39:38Z 2010-09-03T08:39:38Z <p>There is an LLL analogue for arbitrary norms; the original paper by Lovász and Scarf can be found <a href="http://mor.journal.informs.org/cgi/content/abstract/17/3/751" rel="nofollow">here</a>. I recently found a <a href="http://www.cdc.informatik.tu-darmstadt.de/reports/reports/Vanya_Ivanova.bachelor.pdf" rel="nofollow">bachelor thesis</a> on <i>lattice reduction in infinity norm</i>, which contains several other references (for example, work by Kaib and Ritter).</p> http://mathoverflow.net/questions/37273/products-of-linear-forms-in-3-variables/37279#37279 Answer by felix for Products of linear forms in 3 variables felix 2010-08-31T16:38:28Z 2010-08-31T16:38:28Z <p>This should be a comment to Robin's answer.</p> <p>Take any irreducible polynomial $f \in \mathbb{Q}[x]$ of degree 3 with real roots, say $\alpha, \beta, \gamma$. Set $f_1 = x + \alpha y + \alpha^2 z$, $f_2 = x + \beta y + \beta^2 z$, $f_3 = x + \gamma y + \gamma^2 z$.</p> <p>You can find plenty of polynomials <a href="http://www.cems.uvm.edu/~voight/nf-tables/3-25.txt" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/36329/bounding-the-product-of-lengths-of-basis-vectors-of-a-unimodular-lattice/36340#36340 Answer by felix for Bounding the product of lengths of basis vectors of a unimodular lattice felix 2010-08-21T23:53:39Z 2010-08-21T23:53:39Z <p>I don't know how good the bound is you can obtain from this, but what about taking a Korkine-Zolotarev reduced basis of $\Lambda$, say $(b_1, \dots, b_n)$: then, by <a href="http://www.springerlink.com/content/yh7k451558438101/" rel="nofollow">this paper</a>, $\|b_i\|_2^2 \le \frac{i + 3}{4} \lambda_i(\Lambda)^2$, where $\lambda_i(\Lambda)$ is the $i$-th successive minimum of $\Lambda$. By Minkowski, $\prod_{i=1}^n \lambda_i(\Lambda) \le \gamma_n^{n/2} \det \Lambda = \gamma_n^{n/2}$ (in your case), $\gamma_n$ being the <a href="http://en.wikipedia.org/wiki/Hermite_constant" rel="nofollow">$n$-th Hermite constant</a>, whence you get $A \le \prod_{i=1}^n \|b_i\|_2 \le \frac{\gamma_n^{n/2}}{2^n} \prod_{i=1}^n \sqrt{i + 3}$.</p> http://mathoverflow.net/questions/36336/bounding-archimedean-lengths-of-fundamental-units/36338#36338 Answer by felix for Bounding archimedean lengths of fundamental units felix 2010-08-21T23:34:25Z 2010-08-21T23:34:25Z <p>This is a comment, but I can't post any as such...</p> <p>In case $r = 1$, there is only one fundamental unit, whence your minimax is exponential in the regulator. So something better is only possible in case $r > 1$.</p> http://mathoverflow.net/questions/33294/linearly-independent-subsets-of-a-free-module/33305#33305 Answer by felix for Linearly independent subsets of a free module felix 2010-07-25T18:00:52Z 2010-07-25T18:00:52Z <p>Assuming that $A$ has a maximal ideal $\mathfrak{m}$ (for example, by using Zorn's Lemma), one can proceed as follows: if $M$ is a free $A$-module with basis $(v_i)_{i\in I}$, then $M \cong A^I$, whence $M / \mathfrak{m} M \cong A^I / \mathfrak{m} A^I \cong (A / \mathfrak{m} A)^I$. This is a vector space over $k := A / \mathfrak{m} A$ of dimension $|I|$. Since over fields, all vector space bases of the same vector space have the same length, and since the $k$-vector space structure of $M / \mathfrak{m} M$ is independent of the choice of the basis, this shows that all $A$-bases of $M$ have the same cardinality.</p> <p>I don't remember where I first saw this though... maybe someone else has a reference? I saw this first in the case that $A = \mathbb{Z}$ and $\mathfrak{m} = (2)$ for free abelian groups $M$, to show that the rank is well-defined.</p> http://mathoverflow.net/questions/28127/how-can-i-minimise-n-y-mod-x-for-known-x-and-y-and-for-a-given-range-of-n/29278#29278 Answer by felix for how can I minimise (n * y) (mod x) for known x and y, and for a given range of n? felix 2010-06-23T20:42:54Z 2010-06-23T20:42:54Z <p>Ok, I thought a bit about the problem, and here is another idea. It does not provide an answer, but might give a new idea. Maybe even the sketched algorithm turns out to work well in practice.</p> <p>Assume we want to find some $n \in \mathbb{Z}$ satisfying $C \le n \le D$ (for some constants $C$ and $D$, which can be assumed to be integers as well) such that $n\cdot y \pmod{x}$ is minimal under this condition.</p> <p>For that, first use the Extended Euclidean Algorithm to compute the GCD $d$ of $x$ and $y$, as well as integers $A, B$ with $d = A x + B y$. Then we can write $d' = A' x + B' y$ with $d', A', B'$ if, and only if, $d' = d t$ for some $t \in \mathbb{Z}$, and $A' = A t + s y/d$, $B' = B t - s x/d$ with $s \in \mathbb{Z}$.</p> <p>Hence, we want to make $t \in \mathbb{N}_{\ge 0}$ as small as possible, while keeping $C \le B t - s x/d \le D$ for some $s \in \mathbb{Z}$. Such an $s$ exists if, and only if, the closed interval $[(B t - D) \frac{d}{x}, (B t - C) \frac{d}{x}]$ contains an integer, or equivalently, if $\lceil(B t - D) \frac{d}{x}\rceil \le (B t - C) \frac{d}{x}$.</p> <p>Now $\lceil\frac{a}{b}\rceil = \frac{a + (-a \pmod{b})}{b}$, whence $\lceil(B t - D) \frac{d}{x}\rceil = \frac{(B t - D) d + (-(B t - D) d \pmod{x})}{x}$. This is $\le (B t - C) \frac{d}{x}$ if, and only if, $(D - B t) d \pmod{x} \le (D - C) d$.</p> <p>Therefore, an equivalent problem is finding the smallest $t \ge 0$ such that $$D - B t \pmod{\tfrac{x}{d}} \le D - C.$$</p> <p>Note that without loss of generality, we can assume that $0 \le B \le \frac{x}{d}$; in fact, in almost every case, we have $B &lt; \frac{x}{d}$ (the only exception is $d = x$ and $B = 1$, $A = 0$, in which $n \cdot y \pmod{x}$ is zero for all $n$). Hence, we can assume that $B d &lt; x$. Moreover, since $1 = A \frac{x}{d} + B \frac{y}{d}$, we see that $B$ and $\frac{x}{d}$ are coprime. In particular, $-B t \pmod{\frac{x}{d}}$, $t \in \mathbb{N}_{\ge 0}$ iterates over every integer the interval $[0, \frac{x}{d})$, including $0$ itself; therefore, we can always find a solution $t$ satisfying $0 \le t &lt; \frac{x}{d}$, which is not surprising when considering the original problem.</p> <p>One could now proceed as follows, which might lead to an algorithm which is fast in practice (in case $x > (D - C) d$): compute several solutions $t$ by choosing some random $T \le B - C$ and computing $t$ such that $D - B t \equiv T \pmod{\frac{x}{d}}$ (i.e. choose $t \equiv (-T + D) \frac{y}{d} \pmod{\frac{x}{d}}$, since $\frac{y}{d}$ is the modular inverse of $B$ modulo $\frac{x}{d}$) and take the minimum $t'$ over all such $t$. Hoping that at least one of these solutions is small, we are left only with a small interval $[0, t']$ to check for smaller solutions. </p> <p>[Note that this is a similar problem to the one we started with: we want to find $T \in [0, D - C]$ such that $(-T + D) \frac{y}{d} \pmod{\frac{x}{d}}$ is minimal, instead of finding $n \in [C, D]$ such that $n \frac{y}{d} \pmod{\frac{x}{d}}$ is minimal.]</p> <p>When we assume that $T \mapsto (-T + D) B^{-1} \pmod{\frac{x}{d}}$ is "random", we can assume that the $t$'s we obtain are randomly distributed in the interval $[0, \frac{x}{d})$, whence $t'$ can be expected to be small. Hence, this algorithm is only faster than just tying all values for $n$ if $t'$ is less than $D - C$, but this can be determined by a simple comparism.</p> http://mathoverflow.net/questions/28127/how-can-i-minimise-n-y-mod-x-for-known-x-and-y-and-for-a-given-range-of-n/29177#29177 Answer by felix for how can I minimise (n * y) (mod x) for known x and y, and for a given range of n? felix 2010-06-23T00:13:17Z 2010-06-23T00:13:17Z <p>This is in fact a comment to Wadim's comment.</p> <p>The Extended Euclidean Algorithm produces a sequence of equations $d_m = a_m x + b_m y$, where the $d_m$ are strictly decreasing until reaching the GCD of $x$ and $y$. If I recall correctly, the quotients $-\frac{b_m}{a_m}$ are the covergents of the continued fraction expansion of $\frac{x}{y}$.</p> <p>Hence, if $-\frac{b_m}{a_m} > 0$, one can choose $n = \lambda |a_m|$ for a small $\lambda$, as suggested by Roland.</p> http://mathoverflow.net/questions/10014/applications-of-the-chinese-remainder-theorem/102014#102014 Comment by felix felix 2012-07-12T06:33:10Z 2012-07-12T06:33:10Z (I was referring to Filippo Alberto Edoardo's post, not to S. Carnahan's comment.) http://mathoverflow.net/questions/10014/applications-of-the-chinese-remainder-theorem/102014#102014 Comment by felix felix 2012-07-12T06:32:22Z 2012-07-12T06:32:22Z I think that's not entirely correct. Schoof's algorithm computes the action of the Frobenius on the $\ell_i$-torsion subgroup of $E(\overline{\mathbb{F}_q})$ for many small $\ell_i$, and uses this to obtain the trace of Frobenius modulo $\ell_i$. Then these traces modulo $\ell_i$ are combined to find the trace itself, which by Hasse-Weil is in a certain interval of length $4 \sqrt{q} + 1$. http://mathoverflow.net/questions/96434/particular-subset-of-integers-generating-rational-numbers Comment by felix felix 2012-05-09T11:42:43Z 2012-05-09T11:42:43Z The representation cannot be unique for all (non-zero) rational numbers, since $-1 = \frac{x}{y}$ implies $-1 = \frac{y}{x}$. As we must have $x \neq y$, we therefore have (at least) two different representations of $-1$. http://mathoverflow.net/questions/93833/irrationality-of-zetan Comment by felix felix 2012-04-12T08:14:47Z 2012-04-12T08:14:47Z Besides that, on the left hand side, you have a converging series (of partial products). Just because the number of 2's in this series goes to infinity, it does not mean that the limit is not a rational number. Consider $\lim_{n\to\infty} \frac{2^n}{2^n + 1} = 1$. http://mathoverflow.net/questions/87563/find-a-bcd-mod-p-where-a-is-very-large Comment by felix felix 2012-02-05T10:12:53Z 2012-02-05T10:12:53Z What is the relation between $a$ and $p$? I assume that $a &lt; p$, but is there anything else you know? Or could $a$ be just anything between 0 and $p$? http://mathoverflow.net/questions/85480/is-there-an-analogue-of-finite-fields-for-products-of-two-prime-powers Comment by felix felix 2012-01-12T14:16:44Z 2012-01-12T14:16:44Z (I should have written, &quot;product of $m \ge 2$ distinct primes&quot;, i.e. these numbers are precisely the non-prime squarefree numbers. 1 is also included in this list.) http://mathoverflow.net/questions/85480/is-there-an-analogue-of-finite-fields-for-products-of-two-prime-powers Comment by felix felix 2012-01-12T14:13:26Z 2012-01-12T14:13:26Z @Matt: but that only works for product of $m$ primes (and not just two), and not for product of two (or more) prime powers. http://mathoverflow.net/questions/85480/is-there-an-analogue-of-finite-fields-for-products-of-two-prime-powers Comment by felix felix 2012-01-12T13:42:43Z 2012-01-12T13:42:43Z (This also works for numbers with precisely $m$ prime factors: use such rings with precisely $2^m$ idempotent elements. And as with finite fields, such rings are unique up to isomorphism.) http://mathoverflow.net/questions/85480/is-there-an-analogue-of-finite-fields-for-products-of-two-prime-powers Comment by felix felix 2012-01-12T13:15:13Z 2012-01-12T13:15:13Z You could classify products of two finite fields as finite commutative unitary rings which have precisely four idempotent elements and which are reduced (i.e. no nilpotent elements). Would a statement of $P(n)$ using this classification of products of two finite fields be acceptable? http://mathoverflow.net/questions/80874/why-polynomial-gxx-2-x-has-exactly-has-two-roots-in-any-ring-of-the-form-z-p Comment by felix felix 2011-11-14T07:48:04Z 2011-11-14T07:48:04Z Please read the FAQ: this sort of question is not appropriate for mathoverflow. Ask it at math.stackexchange.com instead. http://mathoverflow.net/questions/79181/about-the-sumj-of-the-elements-of-a-subgroup-mod-n Comment by felix felix 2011-10-26T19:03:02Z 2011-10-26T19:03:02Z So you ask for $\sum_{h \in \langle g \rangle \subseteq (\mathbb{Z}/n\mathbb{Z})^*} h$ for $g \in (\mathbb{Z}/n\mathbb{Z})^*$? For $g = 1$, this is most certainly 1. If $\langle g \rangle = (\mathbb{Z}/n\mathbb{Z})^*$, then the sum equals 0. More precisely, the sum equals 0 if the subgroup generated by $g$ contains $-1$. http://mathoverflow.net/questions/78818/how-can-i-reform-this-sequence Comment by felix felix 2011-10-22T09:23:13Z 2011-10-22T09:23:13Z If that's helpful for anyone, here is a Maple function which computes all values of $\Phi$ bounded by $N$: Phi := N -&gt; convert({ seq(n, n=1..N) } intersect { seq(seq(n + k + 2*n*k + 4 * floor((n+1)/2) * floor((k+1)/2), k=1..floor((N-n)/(1+2*n))), n=1..N) }, list); http://mathoverflow.net/questions/78581/feasibility-of-linear-equations-with-few-variables-mod-k Comment by felix felix 2011-10-19T17:15:32Z 2011-10-19T17:15:32Z By faster, you mean faster than computing a Hermite normal form of A modulo k? http://mathoverflow.net/questions/78539/what-is-teh-exact-definition-of-a-rational-power Comment by felix felix 2011-10-19T07:20:32Z 2011-10-19T07:20:32Z In the first link, Wolfram alpha parsed your input as &quot;(x^2)/3&quot;, and in the second, as &quot;x^(1/3)&quot;. Use brackets to make sure Wolfram alpha (and everyone else) understands your notation the way you intend it to be. http://mathoverflow.net/questions/76330/elementary-number-theory Comment by felix felix 2011-09-25T15:22:01Z 2011-09-25T15:22:01Z One can restrict to invertible ideals, and in that case, one still obtains I group. But that's a bit like cheating...