A generalisation of triangle numbers

Consider the sequences:

$\bullet 1, 2, 3, 4,\ldots$
$\bullet 1, 3, 5, 7, \ldots$
$\bullet 1, 4, 7, 10, \ldots$

Formally we define the sequences $(a(n))$ by:
$(a(n))_k = 1 + n(k-1)$ for all $n, k >= 1.$

Summing the first $k$ members of $a(1)$ gives the $k$th triangle number.
Summing the first $k$ members of $a(2)$ gives the $k$th quadratic number.

So, let’s generalise this:

Let $S(n)$ be the set of numbers that you get by summing the first members of $a(n)$; formally, set $S(n)=\{s\in \mathbb{N} : (\exists k\in \mathbb{N}):s = \sum_{i=1}^k(a(n))_i\}$. So $S(1)$ is the set of triangle numbers, $S(2)$ is the set of quadratic numbers, and so on. Let $S = \bigcup_{n=1}^\infty S(n)$.

Problems:
(1) Is $\mathbb{N}\setminus S$ bounded? (Equivalently, is there a positive integer $p\in \mathbb{N}$ such that for all $n\in \mathbb{N}$ with $n\geq p$ we have $n\in S$?).

(2) If the answer to (1) is negative, what is the value of

$\lim\inf_{n\to\infty}\frac{|\{1,\ldots,n\}\cap S|}{n}$?

Measuring subsets of N

Recently I tried to put a measure on the powerset of the natural numbers $\mathcal{P}(\mathbb{N})$, but it was pointed out in a comment that the map I defined is not even finitely additive.

Question: Is there a map $\mu:\mathcal{P}(\mathbb{N}) \to [0, 1]$ with the following properties:

• $\mu(\mathbb{N}) = 1$;
• if $A, B\subseteq\mathbb{N}$ such that $A\cap B = \emptyset$ then $\mu(A\cup B) = \mu(A)+\mu(B)$;
• $\mu$ is translation-invariant, that is $\mu(A+n) = \mu(A)$ for $A\subseteq \mathbb{N}$ and $n\in\mathbb{N}$ where $A+n = \{a+n: a \in A\}$.
Posted in Uncategorized | 1 Comment

Recently I was trying to put a “meaningful” measure on the set $\mathbb{N}$ of natural numbers. The first idea was to measure the density of a subset $A \subseteq \mathbb{N}$ on natural intervals $\{1,\ldots,n\}$ and take the limit of it, that is

$\lim_{n\to\infty}\frac{|\{1,\ldots,n\} \cap A|}{n}.$

However, the limit does not always exist (examples?). So here is a modification and we define a map $\mu:\mathcal{P}(\mathbb{N}) \to [0,1]$ by

$\mu(A) := \lim\inf_{n\to\infty}\frac{|\{1,\ldots,n\} \cap A|}{n}$ for all $A \subseteq \mathbb{N}$.

Question: is $\mu$ additive, that is for $A,B\subseteq \mathbb{N}$ with $A\cap B = \emptyset$ do we have $\mu(A\cup B) = \mu(A) + \mu(B)$? There is a surprising answer that I’ll post in a few days.

Posted in Uncategorized | 1 Comment

The Friendship Paradox says that your friends are likely to have more friends on average than you do. I was wondering whether there are settings in which the statement of the Friendship Paradox does not hold. Below we think about this question in precise mathematical terminology.

Friendships, social networks, and the like are often modelled using simple graphs. People are represented by vertices, and each edge denotes a pair of friends. The set of friends, or neighbors, of a vertex $v$ is defined to be $N(v) = \{w \in V(G) : \{v,w\} \in E(G)\}$. The number of friends, or the degree of $v\in V(G)$ is set to be $\textrm{deg}(v) = \textrm{card}(N(v)$ and the average number of the friends of a person’s friends is defined by $\textrm{ad}(v) = \textrm{avg}\{\textrm{deg}(w) : w \in N(v)\}$.

We say that a person (or vertex) $v$ is proud if $\textrm{deg}(v) > 0$ and $\textrm{deg}(v) > \textrm{ad}(v)$. One interesting version of the question above is: Do there exist graphs such that more than half of the people are proud?

The following insight is elementary, but it was still a surprise for me: It turns out that the share of proud people can be arbitrarily close to $1$.. In order to prove this, take any integer $m > 4$ and consider the complete graph on $m$ points with one edge removed. It is easy to see that the 2 people adjacent to the sole edge that was removed are the only ones that are not proud. So the share of proud people is $\frac{m-2}{m}$ which converges to $1$ as $m$ grows large.

Two-dimensional convergence

Here is something that I was certain would have an easy-to-prove positive answer; but it turns out that there is an exceedingly simple counterexample.

Let $\omega$ be the first infinite ordinal; its successor is $\omega + 1 = \omega \cup \{\omega\}$.We consider a map $M: (\omega+1) \times (\omega+1) \to \mathbb{R}$, or put differently, a $(\omega+1) \times (\omega+1)$-Matrix $M$ of real numbers.

We assume that $M$ has the following properties:
(1) For all $k\in \omega$ we have $\lim_{n\to\infty} M(k, n) = M(k,\omega)$, or more informally, we have “convergence to the right”.
(2) For all $k\in \omega$ we have $\lim_{n\to\infty} M(n, k) = M(\omega, k)$, or more informally, we have “convergence to the bottom”.
(3) $\lim_{n\to\infty} M(n,\omega) = M(\omega,\omega)$, or more informally, the right-hand entries of $M$ converge to the bottom right element $M(\omega,\omega)$.

Question: Does this imply that $\lim_{n\to\infty} M(\omega,n) = M(\omega,\omega)$, that is, do the bottom entries of $M$ also converge to  $M(\omega,\omega)$?

Answer: There is, surprisingly (to me, at least) an easy example showing that the answer is No. Let $M: (\omega+1)^2 \to \mathbb{R}$ be defined by $(\alpha,\beta)\mapsto 0$ if $\alpha \leq \beta$ and $(\alpha,\beta)\mapsto 1$ otherwise. It is easy to verify that (1), (2), (3) above are satisfied. Note that the right-hand entries $M(n, \omega)$ are all 0, and they trivially converge to $M(\omega,\omega) = 0$; but we have $M(\omega, n) = 1$ for all $n\in\omega$ therefore $\lim_{n\to\infty} M(\omega,n) = 1\neq 0 =M(\omega,\omega)$.

For the kind of two-dimensional convergence we are looking for we need some form of “simultaneous” convergence (conceptually related to uniform convergence), which I might address in a later post.

A mathematical view on the notion of “median”

These days we hear about medians of all kinds of things: household income, lifetime of items such as lightbulbs, and so on. It’s time to get a rigorous grip on the concept.

Definition. Suppose $X\neq \emptyset$ is a set, $(C, \leq)$ a totally ordered set, and $f: X \to C$ a function. Then $m\in C$ is said to be a median of $f$ if the sets $\{x \in X : f(x) \leq m\}$ and  $\{x \in X : f(x) \geq m\}$ have equal size.

It is a reflex of mathematicians to ask about existence and uniqueness of any concept they stumble upon. (Note that I wrote “a median” and not “the median” above.) Indeed, as much as the definition above seems to make sense: Even for simple example, the median needs not exist. Let $X = \{1,2,3\}$ and let $f:X\to \mathbb{R}$ be defined by $f(1) = f(2) = 0$ and $f(3) = 1$. Then $f$ has no median according to the definition above. On the other hand, if $X = \{1,2\}$ and $f:X\to \mathbb{R}$ is the inclusion map, then every element of the open interval $]1,2[$ is a median!

There are many common fixes to the problems of existence and uniqueness, but no definition is really elegant. (Most resort to listing the elements in ascending order and to pick the arithmetical middle of the “middle elements” in the list or something similar.)

Other difficulties arise when we want to pick medians of infinite sample sets. Let $(C,\leq)$ be a totally ordered set. We say that $m\in C$ is a median of $C$ if the sets $\{c \in C : c \leq m\}$ and  $\{c \in C : c \geq m\}$ have equal cardinality. Note that in $\mathbb{R}$ every element is a median, but $\mathbb{N}$ has no median at all!

In Adventswoche $k$ (für $k = 1,\ldots, 4$) werden $k$ Kerzen gewählt, angezündet, und so lange brennen gelassen, bis sie 1cm an ihrer Höhe eingebüsst haben. (Die Kerzen sind initial $n$ cm hoch.)
Für $k = 1,2,3$ sei $m_k$ die Anzahl Male, die ich die Kerzen in Woche $k$ anzünde und genau 1cm abbrennen lasse. Für welche Tupel $(m_1, m_2, m_3)$ kann ich für den Anfang der Woche 4 Gleichstand erreichen, sodass die Kerzen am Ende der Adventszeit schön gleichzeitig abbrennen?