math.blogoverflow.comStack Exchange Mathematics Blog - mathblogoverflowcom

 current community chat Mathematics Mathematics Meta more communities Explore other Stack Exchange communities on stackexchange.com Stack Exchange This page is an archive of this blog, and is presented for historical purposes only. Some Statistics on the Growth of Math.SE May 10, 2015 by mixedmath . 11 comments (or How I implemented an unanswered question tracker and began to grasp the size of the site.) I’m not sure when it happened, but Math.StackExchange is huge. I remember a distant time when you could, if you really wanted to, read all the traffic on the site. I wouldn’t recommend trying that anymore. I didn’t realize just how vast MSE had become until I revisited a chatroom dedicated to answering old, unanswered questions, The Crusade of Answers . The users there especially like finding old, secretly answered questions that are still on the unanswered queue — either because the answers were never upvoted, or because the answer occurred in the comments. Why do they do this? You’d have to ask them. But I think they might do it to reduce clutter. Sometimes, I want to write a good answer to a good question (usually as a thesis-writing deterrence strategy). And when I want to write a good answer to a good question, I often turn to the unanswered queue. Writing good answers to already-well-answered questions is, well, duplicated effort. [Worse is writing a good answer to a duplicate question, which is really duplicated effort. The worst is when the older version has the same, maybe an even better answer]. The front page passes by so quickly and so much is answered by really fast gunslingers . But the unanswered queue doesn’t have that problem, and might even lead to me learning something along the way. In this way, reducing clutter might help Optimize for Pearls, not Sand . [As an aside, having a reasonable, hackable math search engine would also help. It would be downright amazing] And so I found myself back in The Crusade of Answers chat, reading others’ progress on answering and eliminating the unanswered queue. I thought to myself How many unanswered questions are asked each day? So I wrote a script that updates and ultimately feeds The Crusade of Answers with the number of unanswered questions that day, and the change from the previous day at around 6pm Eastern US time each day. I had no idea that 166 more questions were asked than answered on a given day. There are only four sites on the StackExchange network that get 166 questions per day (SO, MathSE, AskUbuntu, and SU, in order from big to small). Just how big are we getting? The rest of this post is all about trying to understand some of our growth through statistics and pretty pictures. See everything else below the fold . more » Filed under all levels , expository Tagged: data-analysis , meta , statistics On the Möbius function April 11, 2015 by Sabyasachi Mukherjee . 7 comments The Möbius function is a rather useful one, especially when dealing with multiplicative functions. But first of all, a few definitions are in order. Definition 1 : Let \(\omega(n)\) be the number of distinct prime divisors of \(n\). Definition 2 : The Möbius function, \(\mu(n)\) is defined as \((-1)^{\omega(n)}\) if \(n\) is square-free and \(0\) otherwise. (A number \(n\) is square-free if there is no prime \(p\) such that \(p^2\) divides \(n\).) It may be a good idea to compute the following: \(\omega(n)\) and \(\mu(n)\) for \(n=64, 12, 17, 1\) to get an idea of what’s going on. A Möbius function is an arithmetic function, i.e. a function from \(\mathbb{N}\) to \(\mathbb{C}\). Can you think of some other arithmetic functions? Definition 3:  If \(f(n)\) is an arithmetic function not identically zero such that \(f(m)f(n)=f(mn)\) for every pair of positive integers \(m, n\) satisfying \((m,n)=1\), then \(f(n)\) is multiplicative. Theorem 0 : \(\mu(n)\) is a multiplicative function. Proof : The proof is left to the reader. Theorem 1 : If \(f(n)\) is a multiplicative function, so is \(\displaystyle \sum_{d|n} f(d)\). Before we jump to the proof, let us be clear on the notation. For \(n=12\), \(\displaystyle \sum_{d|n} f(d)=f(1)+f(2)+f(3)+f(4)+f(6)+f(12)\) i.e. the sum taken over the divisors of \(n\). Proof : Consider the sets \(A= \{d :  0<d, d|n \}\) and \(B= \{d_1d_2 : d_1|m_1, d_2|m_2, (m_1,m_2)=1,m_1m_2=n\}\). (Note that such \(m_1, m_2\) exist. Take \(m_1=1,m_2=n\)). Now take \(d \in A\). Then \(1\cdot d\) divides \(1\cdot n\) which means that \(d \in B\) and so \(A \subset B\). Now take \(s \in B\). So \(s\) is of the form \(d_1d_2\) where \(d_1|m_1\) and \(d_2 |m_2\) such that \((m_1,m_2)=1\) with their product \(n\). So, \(s\) divides \(m\) and hence \(B \subset A\). From these, we infer that \(A=B\). Now, suppose that \((m,n)=1\). Then \(\displaystyle F(mn)=\sum_{d|mn} f(d)=\sum_{d_1|m,d_2|n,d_1d_2=mn}f(d_1d_2)=\sum_{d_1|m}\sum_{d_2|n} f(d_1d_2)\) So, $$F(mn)=\sum_{d_1|m}\sum_{d_2|n}f(d_1)f(d_2)(\text{since f is multiplicative})=\sum_{d_1|m}f(d_1)\sum_{d_2|n}f(d_2).$$ Now with this theorem in hand, let us a prove a few more theorems.  Theorem 2 : \(\displaystyle \sum_{d|n} \mu(d)\) is \(0\) if \(n>1\) and \(1\) if \(n=1\). Proof : The case \(n=1\) is trivial. Suppose that \(n>1\). Since \(\mu(n)\) is multiplicative, so is \(\displaystyle F(n)= \sum_{d|n} \mu(d)\). Now let us recall that \(n>1\) can be written as a product of primes, say \(\displaystyle n=p_i^{a_i}\dots p_k^{a_k}\). So, we can write \(F(n)=F(p_1^{a^1})\dots F(p_k^{a_k})\). As \(a_i\ge 1\), \(F(p_i^{a_i})= 0\) (using the definition of \(\mu\).)That means \(F(n)=0\). The desired conclusion now follows from this discussion. Before we now move on to a theorem which shows a connection between the Euler’s \(\varphi-\)function and the Möbius function, let us state a really important theorem, also known as the Möbius Inversion formula. Theorem 3 : If \(\displaystyle F(n)=\sum_{d|n}f(d)\) for every positive integer \(n\), then \(\displaystyle  f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\). Proof:  We will flesh this proof in somewhat lesser detail because we have developed most of the techniques related to his proof. Note that \(\displaystyle \sum_{d|n}\mu(d)F(\frac{n}{d})\) \(\displaystyle =\sum_{d|n}\mu(d)\sum_{k|(n/d)} f(k)= \sum_{dk|n}\mu(d)f(k)=\sum_{dk|n}\mu(k)f(d)\). Can the reader now complete the proof? (Hint: Use Theorem 2 ). Theorem 4 : \(\displaystyle \varphi(n)= n\sum_{d|n} \frac{\mu(d)}{d}.\) Proof:  To write the proof, we use a lemma. Lemma: \(\displaystyle \sum_{d|n} \varphi(d)=n\). Proof of the lemma : Note that for \(n=1\), this is true. Suppose that \(n>1\). Then \(\displaystyle n=p_1^{a_1}\dots p_k^{a_k}\) for some primes \(p_1,\dots, p_k\). As \(\varphi(n)\) is multiplicative, so is \(\displaystyle  F(n)= \sum_{d|n} \varphi(d)\) That means \(\displaystyle F(n)=\prod_{i=1}^k F(p_i^{a_i})\). A quick calculation reveals that \(F(p_i^{a_i})=p_i^{a_i}\) which gives \(F(n)=n\). We can now use this lemma and  the Möbius Inversion formula to finish off the proof. Here as some other problems on multiplicative functions. Problem 1:  \(\displaystyle \frac{1}{\varphi(n)}=\frac{1}{n}\sum_{d|n}\frac{\mu(d)^2}{\varphi(d)}\). Problem 2:  For each positive integer \(n\), \(\displaystyle \mu(n)\mu(n+1)\mu(n+2)\mu(n+3) = 0\). Problem 3: \(\displaystyle \sum_{d|n}|\mu(d)| = 2^{\omega(n)}\). Filed under High School , Undergraduate Tagged: elementary-number-theory , Mobius function When can we do induction? March 10, 2015 by Tobias Kildetoft . 5 comments Introduction Every so often, the question comes up (either here or elsewhere) of why induction is a valid proof technique. And this is of course a very natural question. Induction is after all rather mysterious compared to the other usual proof techniques. At the same time, it is a very useful one, so it is important that people can be given a satisfactory answer. The question is more precisely “why can we do induction on the natural numbers”, but I am not going to a...