10
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Jochen Wengenroth
    Commented Oct 7, 2015 at 12:20
  • $\begingroup$ Why do you expect to stop in a finite number of steps? $\endgroup$
    – Paolo Leonetti
    Commented Oct 7, 2015 at 12:24
  • $\begingroup$ If you want to stop at a given $k$, just take $A_k=\mathbb N \setminus (A_1\cup\cdots\cup A_{k-1})$. $\endgroup$
    – Jochen Wengenroth
    Commented Oct 7, 2015 at 13:30
  • 2
    $\begingroup$ @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$). $\endgroup$
    – Salvo Tringali
    Commented Oct 7, 2015 at 13:39
  • $\begingroup$ Okay, I see the problem. For $k=2$ and $A_2=A_1^c$ it may happen that $f(A_2)=1$. $\endgroup$
    – Jochen Wengenroth
    Commented Oct 7, 2015 at 13:40

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Salvo Tringali
    Commented Oct 7, 2015 at 20:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sean Eberhard
    Commented Oct 8, 2015 at 11:14
  • $\begingroup$ @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. $\endgroup$
    – Salvo Tringali
    Commented Oct 8, 2015 at 17:40
  • $\begingroup$ Anyway, this upper exponential density also seems to work. $\endgroup$
    – Ilya Bogdanov
    Commented Oct 8, 2015 at 18:49
  • 2
    $\begingroup$ @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. $\endgroup$
    – Salvo Tringali
    Commented Oct 16, 2015 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .