User someone - MathOverflow

Answer by Someone for Why should one still teach Riemann integration?

2011-01-21T10:14:36Z

hilbertthm90 and Maxime Bourrigan mentioned already in the comments to the question that the Henstock-Kurzweil integral offers a good alternative to the Riemann integral (see also the lecture notes referred to by Maxime) for a course offered for mathematicians.

The definition of the Henstock-Kurzweil integral is very similar to Riemann's integral: It is also defined using Riemann sums $\sum_{i=1}^n f(t_i) (x_i - x_{i-1})\;$, but instead of letting $\delta = \mathop{max} (x_i - x_{i-1})\;$ approach $0$, one considers for gauge functions $\delta : [a, b] \to \mathbb{R}_{>0}\;$ compatible tagged partitions $(t_i, [x_{i-1}, x_i])_i\;$ with $t_i - \delta(t_i)< x_{i-1}\le t_i \le x_i < t_i +\delta(t_i)\;\;$ and then defines the integral in essential the same way (for details see the wikipedia article).

Dropping the condition $t_i \in [x_{i-1}, x_i]$ one gets an integral (McShane integral) equivalent to the Lebesgue integral on the line, whereas the Henstock-Kurzweil integral works also for "non-absolutely convergent" cases like $\int_0^1 \frac{\mathop{sin}(1/x)}{x} dx\;$.

As one gets all the nice theorems (monotone convergence theorem, dominated convergence theorem, second fundamental theorem of calculus, Lebesgue differentiation theorem) for the cost of a slightly (?) more difficult definition, there shouldn't be any reason (besides tradition) for teaching Riemann integration on $\mathbb R$ to mathematically moderately mature students (and traditions can be satisfied by mentioning that restricting to constant gauge functions gives the Riemann integral).

For more than one dimension (maybe in a second course), one can/should/must then teach Lebesgue integration. Here I have to add from my own experience (I got introduced to integrals equivalent to Lebesgue's in at least five different courses) that a clean separation between measure theory and topology at the beginning like it is done e.g. in Heinz Bauer's "Measure and integration theory" helps enormously for a deeper understanding.

Answer by Someone for Fastest way to factor integers < 2^60

2012-11-22T14:16:25Z

A good source for highly efficient algorithms and implementations for this kind of problems is Dan Bernstein's homepage. There I found an algorithms that might be useful for weeding out all the small prime factors:

If you have $y/(\log y)^{O(1)}\;$ integers, each with at most $(\log y)^{O(1)}\;$ bits, then you can find all the small prime factors of each integer in time $(\log y)^{O(1)}\;$ per integer.

[I didn't look at the details, so you will have to give it a try to see if 60-bit numbers are already big enough.]

Answer by Someone for Can we ascertain that there exist an epimorphism $G\rightarrow H?$

2012-11-05T14:33:46Z

[Slightly too long for a comment, so I post it community wiki answer.]

The kernel of the epimorphism $\quad\varphi : G\times G \to H\times H\quad$ is a normal subgroup of $G\times G$, for which by an easy calculation one can show that

$$N_{-}:=[\pi_1(N), G]\times [\pi_2(N), G] \le N \le \pi_1(N)\times \pi_2(N)$$

with $\pi_i$ the projection on the $i$-th coordinate. As $G$ acts trivially on $\pi_i(N)/[\pi_i(N), G]\;$, $N/N_{-}$ is central in $(G\times G)/N_{-}\;$. [This might be the motivation for Yves' second comment.]

Similar statements hold for the preimages $\varphi^{-1}(H \times 1)$ and $\varphi^{-1}(1 \times H)$ , one can also play around with Goursat's lemma, but I'm still undecided if I should rather try to prove or disprove the question.

Bounding a signed sum of complex numbers

2012-05-29T15:17:11Z

Let $z_i \in \mathbb{C}\:$ for $i=1,\dots, n\;$ be complex numbers, all with absolute value $|z_i|\le 1\;$.

Prove (or disprove) that there exists a choice of signs $s_i \in \{\pm 1\}$ such that $$\left|\sum_{i=1}^n s_i\cdot z_i\right| \le \sqrt{2}.$$

[My interest in this problem is purely for fun. I couldn't solve it a long time ago, forgot about it, but shortly ago it came back into my mind again.]

Answer by Someone for Mathematical "urban legends"

2011-04-13T13:00:00Z

Ed Dean linked to this story in a comment, but I think it is too nice to stay hidden there:

On December 5, 1947, Einstein and Morgenstern accompanied Gödel to his U.S. citizenship exam, where they acted as witnesses. Gödel had confided in them that he had discovered an inconsistency in the U.S. Constitution, one that would allow the U.S. to become a dictatorship. Einstein and Morgenstern were concerned that their friend's unpredictable behavior might jeopardize his chances. Fortunately, the judge turned out to be Phillip Forman. Forman knew Einstein and had administered the oath at Einstein's own citizenship hearing. Everything went smoothly until Forman happened to ask Gödel if he thought a dictatorship like the Nazi regime could happen in the U.S. Gödel then started to explain his discovery to Forman. Forman understood what was going on, cut Gödel off, and moved the hearing on to other questions and a routine conclusion.

(cited from wikipedia)

EDIT: Thanks to Gerald Edgar (and Google) you can find the answer to what the loophole in the US Constitution is here.

Answer by Someone for Can we unify addition and multiplication into one binary operation? To what extent can we find universal binary operations?

2011-05-13T16:14:43Z

How about this alternative approach to answer Q1:

Step 1: Get some room by defining first the diagonal of $*$ (which is mapped to numbers divisible by $5$):

$z*z := 5z$ for $z > 0$ and $z*z := 5z-5$ for $z <= 0$.

Now we define the meaning of $x*y$ for $x\ne y$ depending on $x \bmod 5$ and $y \bmod 5$.

Step 2: We recode all integers in different ways (to signal if we want to add or multiply)

$z * (z*z) := 5z+1$ (special $x*y$ for $y = 0 \bmod 5$ and $x \ne y$).
$(z*z) * (z*(z*z)) := 5z+2$ (special $x*y$ for $x = 0 \bmod 5$ and $y = 1 \bmod 5$).
$(z*z) * ((z*z) * (z*(z*z))) := 5z+3$ (special $x*y$ for $x = 0 \bmod 5$ and $y = 2 \bmod 5$).

Step 3: We define the addition and the multiplication

$(y*(y*y)) * ((z*z) * (z*(z*z))) := y + z$ (special $x*y$ for $x = 1 \bmod 5$ and $y = 2 \bmod 5$).
$(y*(y*y)) * ((z*z) * ((z*z) * (z*(z*z)))) := y \cdot z$ (special $x*y$ for $x = 1 \bmod 5$ and $y = 3 \bmod 5$).

The still undefined values of $x*y$ can be assigned arbitrarily. The last two definitions give the formulas for addition and multiplication.

Answer by Someone for Never appeared forthcoming papers

2010-12-07T09:00:16Z

How about "The classification of finite quasithin groups" by G. Mason from 1980? The classification of finite simple groups was announced when G. Mason was still working on this important case and he then abandoned the work. This hole in the classification was closed finally in 2004 by M. Aschbacher and S. D. Smith.

Answer by Someone for Is P=NP relevant to finding proofs of everyday mathematical propositions?

2010-12-02T09:42:38Z

The paper "A Personal View of Average-Case Complexity" by Russell Impagliazzo considers five different worlds depending on the average case complexity of NP-complete problems, one of them ("Algorithmica") having P=NP.

The different worlds are explained using the famous anecdote of Gauss and his teacher asking the class to add the numbers from 1 until 100, so it's a nice read for any mathematician. The focus of the article is on the consequences of the five different possibilities on the teacher being able to pose problems for which he knows the solution but which Gauss cannot solve. So it doesn't answer your question about "a trick to turn mathematics into NP-problems", but gives you an idea about the question in your title.

Answer by Someone for Jokes in the sense of Littlewood: examples?

2010-09-16T14:00:25Z

In characteristic $p$, the so-called biologists' rule

$$(a+b)^p = a^p + b^p$$ (which got its name by mathematics students that worked as teaching assistants for "mathematics for biologists") is correct.

Answer by Someone for What are some interesting corollaries of the classification of finite simple groups?

2010-08-03T08:42:45Z

Citing Graham's answers 1 and 2 to two other questions:

Definition: A polynomial $f(x)\in \mathbb C[x]$ is indecomposable if whenever $f(x)=g(h(x))$ for polynomials $g$, $h$, one of $g$ or $h$ is linear.

Theorem. Let $f, g$, be nonconstant indecomposable polynomials over $\mathbb C$. Suppose that $f(x)−g(y)$ factors in $\mathbb C[x,y]$. Then either $g(x)=f(ax+b)$ for some $a, b \in \mathbb C$, or

$$\deg f=\deg g=7,11,13,15,21, \mbox{or } 31,$$

and each of these possibilities does occur.

The proof uses the classification of the finite simple groups and is due to Fried [1980, in the proceedings of the 1979 Santa Cruz conference on finite groups], following a the reduction of the problem to a group/Galois-theoretic statement by Cassels [1970]. [W. Feit, "Some consequences of the classification of finite simple groups," 1980.]

Answer by Someone for Does an "efficient" random number generator exist?

2010-07-21T10:11:27Z

If you need your random sequence unpredictable in a cryptographic sense, then take a look at the article How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle presented by Ben Morris, Phillip Rogaway and Till Stegers at the Crypto 2009 conference last year.

If you don't need cryptographic security, don't bother looking at the article, as other approaches will be much more efficient. By the way, given the cipher you get your random numbers by encrypting the sequence 0, 1, 2, 3, ... mod n and changing randomly the key whenever the current element of the sequence is 0 mod n.

Answer by Someone for Is there a universal countable group? (a countable group containing every countable group as a subgroup)

2010-06-22T09:01:35Z

Hall's universal group is a countable locally finite group that contains every countable locally finite group (see these lecture notes).

Answer by Someone for What are some correct results discovered with incorrect (or no) proofs?

2010-06-11T15:31:04Z

The classification of finite simple groups was announced 1983 when Geoff Mason was still working on the quasithin case. I've heard somewhere that he lost his motivation then and never finished his 600+ pages manuscript. The gap was closed 20 years later by Michael Aschbacher and Steve Smith.

Answer by Someone for "Radon-Nikodym theorem" for nonabsolute continuous measures

2010-05-18T15:23:33Z

You looking for the Lebesgue's decomposition theorem.

Answer by Someone for The Riemann correspondence for riemann surfaces made explicit and its generalizations

2010-05-18T13:10:32Z

You could take a look in Lectures on Riemann surfaces by Otto Forster (Springer, Graduate Texts in Mathematics 81). The book starts at a moderate level (you just need to know basic complex analysis and the Lebesgue integral), but covers quite some topics like the correspondence between Galois groups of field extensions and covering transformations as well as how to remove the removable singularities. I don't have the book available now, but from my memory (of the German original) there should be enough in it to answer at least your first three questions.

PS: You can google for the two terms "forster" and "field of meromorphic functions" to get a link to google books for a first impression of the book.

Answer by Someone for Reference request: given a divisor d of N, how quickly can I obtain the largest factor of N coprime to d?

2010-05-06T14:57:31Z

Take a look at these papers from Dan Bernstein. It's not quite what you are looking for, but he does even more than you need in time $n(\lg n)^{2+o(1)}$ where $n$ = number of bits of $N\cdot d$ (one of the elements of the coprime base will be $n_2$). Maybe your problem can be solved even faster than that.

Answer by Someone for What are the normal subgroups of a direct product?

2010-05-06T14:35:28Z

Let $N$ be normal in $G\times H$. For $n=(n_1, n_2) \in N$ and $(g, 1) \in G\times H$ follows $([n_1, g], 1) = (n_1^{-1}n_1^g, 1) = n^{-1}\cdot n^{(g, 1)} \in N$ (taking the notations used in group theory: $n^g = g^{-1}ng$ etc), i.e., $[\pi_1(N), G]\times 1 \le N$ (where $[A, B]$ denotes the subgroup generated by the commutators $[a, b]$ with $a \in A, b\in B$). Also $1\times[\pi_2(N), H] \le N$, hence $[\pi_1(N), G]\times[\pi_2(N), H] \le N$.

As $[\pi_1(N), G]$ is normal in $G$, one can easily deduce for $G, H$ simple the cases described by Jack Schmidt (and also what happens in the missing case that one of the two groups is abelian but the other one not).

Answer by Someone for Regular borel measures on metric spaces

2010-04-22T11:21:05Z

Every finite Borel measure defined on a Polish space is regular, see e.g., Lemma 26.2 in Heinz Bauer: Measure and Integration Theory.

Comment by Someone

2013-04-30T09:44:50Z

Perfectness doesn't help: Just take the direct product of $k$ copies of $G$ where $k$ is the number of prime divisors of $G$.

Comment by Someone

2013-04-15T12:14:02Z

Your special equation you can first solve $\bmod c$, and then use a solution $s\in \mathbb{Z}$ to write $a = s+a'$ where $a'$ is a multiple of $c$. Now solve for $a'$.

Comment by Someone

2013-04-05T15:28:01Z

@S. Carnahan: Oh, right. Thanks. Even the very first comment corrects already the statement that no such groups are known. It seems worth to read the comments sometimes...

Comment by Someone

2013-04-05T13:41:45Z

Do you ask this because of your interest in the commuting graphs of groups? There seems to be no (finite?) group known to have this property - see [the last sentence here](symomega.wordpress.com/2010/03/02/…).

Comment by Someone

2013-03-21T10:20:08Z

Didn't Gauss publish in Latin?

Comment by Someone

2013-03-19T09:13:50Z

@StefanKohl: Yes, taking $H$ bigger than $Z_p$ doesn't give any improvements. But starting with $n=2$ and $f_p(2)=3$ you can get per induction with $H = Z_p$ upper bounds $f_p(n)\le 3p^{n-2}+(p^{n-2}-1)/(p-1)$. For odd $p$ I get with $f_p(3)=5$ an upper bound of type $O(p^{n-3})$.

Comment by Someone

2013-03-18T15:25:30Z

Did you try calculating $f_p(n)$ for small $n$ like $2$, $3$ or $4$? Maybe you can improve François' bound slightly by combining these results with the fact that every extension $G$ of a group $N$ by a group $H$ (i.e., $G/N = H$ for some embedding of $N$ into $G$) is a subgroup of the wreath product of $N$ by $H$.

Comment by Someone

2012-12-13T10:07:06Z

"largest power of $p$ greater than or equal to $n$"?

Comment by Someone

2012-11-21T16:08:45Z

I just found also mathoverflow.net/questions/97105/… which might be of interest for you.

Comment by Someone

2012-11-21T16:06:27Z

For representations of $H$ over $\mathbb{F}_p$ with $p$ coprime to the order $H$ you get - to my (non-expert) knowledge - only similar behavior as over $\mathbb{C}$ if $\mathbb{F}_p$ contains an $n$-th root for $n$ the exponent of the group $H$ (= least common multiple of the orders of all group elements). See also Geoffrey's answer to mathoverflow.net/questions/91132/…

Comment by Someone

2012-11-21T15:35:15Z

Do I understand you correctly that you mean with "the entire $p'$-group $H$ acts fixed point freely" that each element of $H^#$ acts fixed point freely, whereas in your question you only ask for no nontrivial fixed point for all the group? [For elementwise fixed point free action you surely get strong restrictions on the structure of $H$ - see for example Theorem 8.3.2 in "The Theory of Finite Groups" by Kurzweil/Stellmacher.]

Comment by Someone

2012-11-20T15:49:01Z

Do you know anything nontrivial about finite $p'$-groups $H$ acting fixed point freely on elementary abelian $p$-groups?

Comment by Someone

2012-11-20T13:15:36Z

Maybe too hard? You could have started with the easier question asking which $H$ act fixed point freely on an elementary abelian $p$-group, or -- if you already know the solution to this question -- given your readers some hints about what you know about $H$.

Comment by Someone

2012-09-18T09:47:15Z

crypto.stackexchange.com might be a better place to ask this question.

Comment by Someone

2012-08-02T10:48:10Z

Take a look at the answer to math.stackexchange.com/q/151347/33256 (you should be able to figure it out).