# Does a monotone subadditive $f: \mathcal{P}(\bf N)\to [0,1]$ admit a finite partition with values in $(0,1)$?

A function $f\colon \mathcal{P}(\mathbf{N})\to [0,1]$ is said to have the Darboux property whenever for all $X \subseteq \mathbf{N}$ and $y \in [0,f(X)]$, there exists $Y \subseteq X$ such that $f(Y)=y$.

Moreover, $f$ is said to be monotone if $f(X)\le f(Y)$ whenever $X\subseteq Y$ and subadditive if $f(X\cup Y) \le f(X)+f(Y)$ for all $X,Y \subseteq \mathbf{N}$.

Question. Let $f\colon \mathcal{P}(\mathbf{N})\to [0,1]$ be a monotone subadditive function with the Darboux property such that $f(\mathbf{N})=1$. Does there exist necessarily a finite partition $\{A_1,\ldots,A_k\}$ of $\mathbf{N}$ for which $$f(A_1), \ldots, f(A_k) \in (0,1)?$$

A simpler version of this question has been posted on MSE one week ago here, showing that in general the answer is negative if $k$ is bounded.

The question comes from the study of properties of a class of functions satisfying certain axioms, which can be called as "upper densities" (with this respect, you can see this MO question). Here, instead, there is MO question related to the definition of Darboux property.

A related construction (which does not ask for subadditivity) by Salvo Tringali has been provided here.

• What's wrong with this rather trivial construction: Choose $A_1\subseteq \mathbb N$ with $f(A_1)=1/2$. Because of subadditivity, $1=f(A_1 \cup A_1^c)\le f(A_1)+f(A_1^c)$ so that $f(A_1^c)\ge 1/2$. Next choose $A_2\subseteq A_1^c$ with $f(A_2)=1/4$. As above $f(A_1^c \cup A_2^c)\ge 1/4$. Continue in that way. – Jochen Wengenroth Oct 7 '15 at 12:20
• Why do you expect to stop in a finite number of steps? – Paolo Leonetti Oct 7 '15 at 12:24
• If you want to stop at a given $k$, just take $A_k=\mathbb N \setminus (A_1\cup\cdots\cup A_{k-1})$. – Jochen Wengenroth Oct 7 '15 at 13:30
• @JochenWengenroth. Of course. But only if you can prove that $0 < f((A_1 \cup \cdots \cup A_k)^c) < 1$ for some $k$, in your construction. In principle, you don't have any information on the behaviour of $f(A^c)$ for $A \subseteq \mathbf N$ and $f(A) > 0$ (if $f(A) = 0$, it is seen that $f(A^c) = 1$). – Salvo Tringali Oct 7 '15 at 13:39
• Okay, I see the problem. For $k=2$ and $A_2=A_1^c$ it may happen that $f(A_2)=1$. – Jochen Wengenroth Oct 7 '15 at 13:40

$\let\eps\varepsilon$It seems that the following function fits: $$f(A)=\inf\left\{\alpha\colon \quad \sum_{x\in A}x^{-\alpha}<\infty\right\}.$$ (I assume that $\mathbb N$ starts with 1.) Clearly, it is monotone, and $f(\mathbb N)=1$. Moreover, it is more than subadditive: we have $f(A\cup B)=\max\{f(A),f(B)\}$. This also implies that if $A_1\cup A_2\cup\dots\cup A_k=\mathbb N$, then $f(A_i)=1$ for some $i$.

It remains to show that $f$ has the Darboux property. Let $f(A)=\alpha$ and $\beta\in[0,\alpha)$; we need to find $B\subseteq A$ with $f(B)=\beta$. We have $\sum_{x\in A}x^{-\beta}=\infty$. Set $X_n=[2^n,2^{n+1})\cap \mathbb N$, $A_n=A\cap X_n$, and $a_n=\sum_{x\in A_n}x^{-\beta}$. Then the series $\sum_n a_n$ diverges.

Set $b_n=\min\{a_n,1\}$. The series $\sum_n b_n$ diverges as well (this is trivial if $b_i=1$ infinitely many times, as well as if it happens only finitely many times). Now, choose $B_n$ to be the subset of $A_n$ such that $S_n=\sum_{x\in B_n}x^{-\beta}\leq b_n$, and $S_n$ is maximal subject to this property. Then $S_n\geq b_n/2$ for all $n\geq 1$.

Set $B=\cup_n B_n$; then $\sum_{x\in B}x^{-\beta}\geq \sum_n b_n/2=\infty$. On the other hand, for every $\eps>0$ we have $$\sum_{x\in B}= \sum_n\sum_{x\in B_n}x^{-\beta-\eps} \leq \sum_n 2^{-\eps n}\sum_{x\in B_n}x^{-\beta} \leq \sum_n2^{-\eps n}<\infty.$$ Thus $f(B)=\beta$.

• Very nice. Incidentally, the fnc in this example is also shift-invariant, i.e. $f(X + h) = f(X)$ for all $X \subseteq \mathbf N$ and $h \in \mathbf N$ (immediate by the limit comparison test), and has the strong Darboux property, too: If $A\subseteq B\subseteq \mathbf N$ and $\gamma \in {]f(A), f(B)[}$, then $f$ being weakly Darboux implies the existence of a set $C\subseteq B$ s.t. $f(C) = \gamma$, and hence $f(A \cup C) = \max(f(A), f(C)) = \gamma$. Since, of course, $A \subseteq A \cup C \subseteq B$, that is enough to conclude. – Salvo Tringali Oct 7 '15 at 20:20
• It's very similar (the same?) to take $f(A) = \limsup\,\log|A\cap\{1,\dots,n\}|/\log n.$ This is something like the "upper dimension" of a set of integers. – Sean Eberhard Oct 8 '15 at 11:14
• @SeanEberhard. The fnc in your comment is sometimes called the upper exponential density; see, e.g., G. G. Lorentz, On a problem of additive number theory, Proc. Amer. Math. Soc. 5 (1954), No. 5, 838-841, or Section 4 in: G. Grekos, On various definitions of density (survey), Tatra Mt. Math. Publ. 31 (2005), 17-27. But I don't know if it's the same as the fnc in Ilya Bogdanov's example. – Salvo Tringali Oct 8 '15 at 17:40
• Anyway, this upper exponential density also seems to work. – Ilya Bogdanov Oct 8 '15 at 18:49
• @SeanEberhard. You were right. The fnc in Ilya's answer is called the convergence exponent in the 1st vol. of Pólya and Szegö's Problems and Theorems in Analysis (Pt. I, Chap. 3, Sect. 2), and Exercise 113 on p. 26 (which is solved on pp. 202-203) asks to prove that it is equal to $\limsup_n\frac{\log n}{\log x_n}$, where $(x_n)_{n \ge 1}$ is the natural enumeration of the set $X$ (assuming $|X|=\infty$), and now it's not difficult to see that this latter limit is nothing but the upper exponential density mentioned in your comment. – Salvo Tringali Oct 16 '15 at 20:51