User felix - MathOverflow

Answer by felix for Finiteness conditions and Veronese subrings

2012-04-03T14:05:02Z

In case $G$ is finite, this cannot happen.

(This might extend to the general case of finitely generated groups, as Fred told me when we talked about this in my office :-) )

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.

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}}$.

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.

This shows that $R$ is of finite type over $R_0$.

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$.

Answer by felix for Is there an analogue of finite fields for products of two prime powers?

2012-01-14T15:50:06Z

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.)

Answer by felix for A pair of subset of natural numbers having density, but whose intersection has no density

2011-04-07T07:25:06Z

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$.

Answer by felix for A unique zero of a system of polynomials is a zero of a finite system.

2011-03-02T08:14:02Z

The existence of a finite $S_2$ follows from Hilbert's basis theorem, as $\mathbb{R}$ is obviously Noetherian. Just take a finite generating system of the ideal generated by $S$.

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$.

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 all 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 (variety) of $S$.

How random are unit lattices in number fields?

2010-10-10T22:28:35Z

I was wondering how random unit lattices in number fields are. To make this more precise:

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.

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$.

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$.)

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:

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\| < \varepsilon$ for all $i$?
And if this exists, can one bound the discriminant of $K$ (or any other invariant of $K$) in terms of $\varepsilon$?

(Of course, this question is only interesting when $n > 2$.)

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.

Answer by felix for Methods for solving Pell's equation?

2010-12-04T05:55:27Z

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...)

See for example M. Jacobson, H. Williams: Solving the Pell Equation. Springer, 2009.

Answer by felix for What is the link between sections and sections? (schemes)

2010-09-22T07:18:06Z

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$.

On the other hand, the elements of $\mathcal{O}_X(U)$ can be seen as holomorphic functions on $U$.

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.

Answer by felix for Other norms for Lattice reduction techniques (LLL, PSLQ)?

2010-09-03T08:39:38Z

There is an LLL analogue for arbitrary norms; the original paper by Lovász and Scarf can be found here. I recently found a bachelor thesis on lattice reduction in infinity norm, which contains several other references (for example, work by Kaib and Ritter).

Answer by felix for Products of linear forms in 3 variables

2010-08-31T16:38:28Z

This should be a comment to Robin's answer.

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$.

You can find plenty of polynomials here.

Answer by felix for Bounding the product of lengths of basis vectors of a unimodular lattice

2010-08-21T23:53:39Z

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 this paper, $\|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 $n$-th Hermite constant, 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}$.

Answer by felix for Bounding archimedean lengths of fundamental units

2010-08-21T23:34:25Z

This is a comment, but I can't post any as such...

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$.

Answer by felix for Linearly independent subsets of a free module

2010-07-25T18:00:52Z

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.

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.

Answer by felix for how can I minimise (n * y) (mod x) for known x and y, and for a given range of n?

2010-06-23T20:42:54Z

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.

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.

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}$.

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}$.

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$.

Therefore, an equivalent problem is finding the smallest $t \ge 0$ such that $$D - B t \pmod{\tfrac{x}{d}} \le D - C.$$

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 < \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 < 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 < \frac{x}{d}$, which is not surprising when considering the original problem.

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.

[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.]

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.

Answer by felix for how can I minimise (n * y) (mod x) for known x and y, and for a given range of n?

2010-06-23T00:13:17Z

This is in fact a comment to Wadim's comment.

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}$.

Hence, if $-\frac{b_m}{a_m} > 0$, one can choose $n = \lambda |a_m|$ for a small $\lambda$, as suggested by Roland.

Comment by felix

2012-07-12T06:33:10Z

(I was referring to Filippo Alberto Edoardo's post, not to S. Carnahan's comment.)

Comment by felix

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$.

Comment by felix

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$.

Comment by felix

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$.

Comment by felix

2012-02-05T10:12:53Z

What is the relation between $a$ and $p$? I assume that $a < p$, but is there anything else you know? Or could $a$ be just anything between 0 and $p$?

Comment by felix

2012-01-12T14:16:44Z

(I should have written, "product of $m \ge 2$ distinct primes", i.e. these numbers are precisely the non-prime squarefree numbers. 1 is also included in this list.)

Comment by felix

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.

Comment by felix

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.)

Comment by felix

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?

Comment by felix

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.

Comment by felix

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$.

Comment by felix

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 -> 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);

Comment by felix

2011-10-19T17:15:32Z

By faster, you mean faster than computing a Hermite normal form of A modulo k?

Comment by felix

2011-10-19T07:20:32Z

In the first link, Wolfram alpha parsed your input as "(x^2)/3", and in the second, as "x^(1/3)". Use brackets to make sure Wolfram alpha (and everyone else) understands your notation the way you intend it to be.

Comment by felix

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...