20
$\begingroup$

Relevant Theorems:

$(a)$ There is no continuous function $f$ on $\mathbb{R}$ which takes on every value exactly twice.

$(b)$ There is no continuous function $f$ on $\mathbb{R}$ which takes on each value either $0$ times or $2$ times.

$(c)$ Find a continuous function $f$ on $\mathbb{R}$ which takes on every value exactly $3$ times.

$(d)$ There is no continuous function $f$ on $\mathbb{R}$ which takes on every value exactly $2n$ times , for all $n \in \mathbb{N}$.

Source: Spivak's "Calculus"

Definitions:

Fix a function $f:\mathbb{R}\to\mathbb{R}$ such that $f$ obtains each value only finite (possibly $0$) number of times. We say $E \subset \mathbb{N}$ is "the multiplicity set" of $f$ if
$1$. For every $n \in E$, there exists at least one value that $f$ takes exactly $n$ times.
$2$. If $f$ takes on a value exactly $n$ times, then $n \in E$

In other words, $n \in E$ iff $n$ is the multiplicity of some value under $f$.

A subset $E $ of $N$ is said to be "constructable" iff there exists a continuous function $f$ on $\mathbb{R}$ such that $E$ is the multiplicity set of $f$.

The problem:

With these definitions, it seems like the theorems from Spivak are just telling that the sets $\{2\},\{0,2\},\{2n\}$ cannot be constructed, and, we can construct $\{3\}$.

After this, we can also construct sets like $\{0,1,4\},\{0,2,4\},\{0,1,2,4\},\{4,5\}$ etc.

So far, I have got one theorem about the construction of some sets.

For every continuous function $f$ on $\mathbb{R}$ with multiplicity set $E$, if $E$ has maximum $2n$ then $E$ includes $0$ and some member of $\{1,..,n\}$.

This theorem tells us that sets like $\{0,3,4\}$ are impossible, but doesn't tell anything about sets with odd maximums. So far I don't have anymore theorems to decide whether a set is constructable or not.

Hence, my question is:

If $E$ is a finite subset of $\mathbb{N}$, then is there a way to effectively & efficiently decide whether or not $E$ is constructable or not?

$\endgroup$
14
  • 1
    $\begingroup$ This may be a better fit for MathOverflow, incidentally. $\endgroup$ May 29, 2022 at 20:58
  • 1
    $\begingroup$ I am a beginner in learning calculus, so I may have missed some important considerations. But I tried to work on the multiplicity sets with odd maximums. I take the functions to have $\mathbb{R}$ as their domain. I came to three theorems which I believe are necessary for a set to be a multiplicity set with an odd maximum. If the $E$ is a multiplicity set with more than one element and with an odd maximum, these three theorems need to hold. 1) If $n$ is the odd maximum, then $(n+1)/2\in E$. 2) If $e$ is an even element of $E$, then $(e-1)\in E$. 3) If $1\notin E$, then $(n-1)\in E$. $\endgroup$
    – Kaveh Rad
    May 30, 2022 at 9:35
  • 1
    $\begingroup$ @PrithuBiswas I couldn't construct $\{4,5\}$ and $\{0,3\}$. Could you please provide an example? $\endgroup$
    – Kaveh Rad
    May 30, 2022 at 13:59
  • 1
    $\begingroup$ @KavehRad Here and Here are some examples. $\endgroup$ May 30, 2022 at 14:26
  • 2
    $\begingroup$ A similar problem was in the French TFJM 2014. See problem 6 in tfjm.org/editions-precedentes/#edition2014 . I haven’t looked at the solutions but there may be some interesting ideas (I haven’t seen any official correction so don’t take the students’ solutions as gospel). $\endgroup$
    – Aphelli
    May 31, 2022 at 7:53

1 Answer 1

12
+100
$\begingroup$

The stated criterion is actually sufficient!

Theorem.

Take any finite $S⊆ℕ$. Then $S$ is constructible (i.e. is a multiplicity set of some continuous function from $ℝ{→}ℝ$) iff $S$ has an odd maximum or $S$ has maximum $2n$ and $\{0,k\}⊆S$ for some $k∈\{1..n\}$.

Proof.

Forward implication (the routine part)

Take any $S⊆ℕ$ with maximum $2n$ that is the multiplicity set of some continuous function $f$ from $ℝ{→}ℝ$. Then let $v$ be some value that $f$ takes $2n$ times, and let $x_{1..2n}$ be the points at which $f$ takes value $v$, in increasing order. (That is, $x_1 < \cdots < x_{2n}$, and for every $t∈ℝ$ we have $f(t) = v$ iff $t$ is equal to one of $x_{1..2n}$.) Let $D_i = (x_i,x_{i+1})$ for each $i∈\{1..2n{-}1\}$, and $D_0 = (-∞,x_1)$ and $D_{2n} = (x_{2n},∞)$. Observe that $f$ on each $D_i$ is either completely above $v$ or completely below $v$ (otherwise it would take value $v$ at some point in $D_i$ by IVT). Call $D_{1..2n-1}$ the inner intervals and call $D_0,D_{2n}$ the outer intervals.

Let $p^+$ be the number of inner intervals on which $f$ is completely above $v$.
Let $p^-$ be the number of inner intervals on which $f$ is completely below $v$.
Let $q^+$ be the number of outer intervals on which $f$ is completely above $v$.
Let $q^-$ be the number of outer intervals on which $f$ is completely below $v$.
Note that $p^+ + p^- = 2n-1$ and $q^+ + q^- = 2$.

Let $y_i$ be the midpoint of each inner interval $D_i$, and let $y_0 = x_1-1$ and $y_{2n} = x_{2n}+1$.
Let $h = \min_{i\in\{0..2n\}} \frac12|f(y_i)-v|$.
Then $f$ takes value $(v+h)$ at least $(2p^+ + q^+)$ times (by IVT).
And $f$ takes value $(v-h)$ at least $(2p^- + q^-)$ times (by IVT).
But $f$ takes any value at most $2n$ times.
And $(2p^+ + q^+) + (2p^- + q^-) = 4n$.
Thus $2p^+ + q^+ = 2p^- + q^- = 2n$, and hence $q^+,q^-$ are even, so one of them is zero.

By symmetry we can assume $q^- = 0$. Let $m$ be the minimum value taken by $f$ on $[x_1,x_{2n}]$ (by EVT). Then $(m-1)$ is not a value taken by $f$, since $f$ is completely above $v > m$ on the outer intervals. Therefore $0∈S$.

Now let $x'_{1..c}$ be the points at which $f$ takes value $m$, and let $r$ be $\frac12$ the minimum distance between those points. Let $m' = \min_{i∈\{1..c\}} \frac12|\min(f(x'_i-r),f(x'_i+r))|$. Then $f$ takes value $m'$ at least $2$ times on $[x'_i-r,x'_i+r]$ for each $i∈\{1..c\}$ (by IVT). Therefore $2c ≤ 2n$, and hence $c ∈ \{1..n\}$.

Backward implication (the interesting part)

We shall first prove a stronger version of the theorem, namely that any finite $S⊆ℕ$ that satisfies the given condition is the multiplicity set of some continuous function $f$ from $ℝ→ℝ$ that is grid-based, meaning that there is a countable set $G⊆ℝ$ called its grid-set such that:

  1. $f$ on $ℤ$ takes only values in $G$.
  2. $f(k),f(k+1)$ are adjacent in $G$ for each $k∈ℤ$.
  3. For each $k∈ℤ$, there is some $c∈ℕ^+$ such that $f$ on $[k,k+1]$ takes each value $v∈ℝ$:
    • Exactly $c$ times if $v$ is strictly between $f(k)$ and $f(k+1)$.
    • Zero times if $v$ is strictly below/above both $f(k)$ and $f(k+1)$.

For each $k∈ℤ$, we shall call $f$ on $(k,k+1)$ a segment of $f$ and describe the segment by the notation "$\boldsymbol{(a,c,b)✻}$" such that:

  1. It takes each value $v∈ℝ$:
    • Exactly $a$ times if $v = f(k)$.
    • Exactly $b$ times if $v = f(k+1)$.
    • Exactly $c$ times if $v$ is strictly between $f(k)$ and $f(k+1)$.
  2. "✻" is either "↗" or "↘" indicating $f(k) < f(k+1)$ or $f(k) > f(k+1)$ respectively.

Observe that the multiplicity set of a grid-based function $f$ is completely determined by its grid-set and the description of all the segments of $f$ using just the above notation. Note when counting the number of times the segment of $f$ on $(k,k+1)$ takes value $f(k)$, we do not count the point $k$ itself (and likewise we do not count the point $(k+1)$).

For example, ( ... $(0,1,0)$$(0,1,0)$$(0,1,0)$↗ ... ) describes a grid-based monotonic continuous function from $ℝ→ℝ$. If its grid-set is $ℤ$, then its multiplicity set is $\{1\}$. If its grid-set is $ℕ^+∪\frac1{ℕ^+}$, then its multiplicity set is $\{0,1\}$ (since it stays above the real-axis).

For another example, ( ... $(2,5,2)$$(0,1,0)$$(0,3,0)$$(0,1,0)$$(2,5,2)$↗ ... ) is illustrated by the following diagram:

Multiplicity set {4,5} achieved by ( ... (2,5,2)↗ (0,1,0)↗ (0,3,0)↘ (0,1,0)↗ (2,5,2)↗ ... )

And this example can be used to achieve multiplicity set $\{4,5\}$ using grid-set $ℤ$ and multiplicity set $\{0,4,5\}$ using grid-set $ℕ^+∪\frac1{ℕ^+}$. It is easy to verify this from the diagram by adding the numbers in each row plus one for each grid-point (indicated in the diagram by the horizontal dashes).

Now, what type of segments can we build, and how can we put them together to build the desired solutions? It turns out that we only need two basic ingredients, namely the straight segment and compactification, which we can use to build segment type $(i,2k+1,j)$ for any $i,j,k∈ℕ$ such that $i,j ≤ k$.

Let $L$ be the straight segment, which is simply of type $(0,1,0)$. Alternating up and down yields the segment type $(k,2k+1,k)$ = ( ( $L$$L$↘ )$^k$ $L$↗ ). Compactifying it on the right yields the segment type $(k,2k+1,0)$, which is easily understood from the diagram below (illustrating the segment type $(2,5,0)$):

(2,5,2)↗ (2,5,2)↗ ... compactified on the right

Compactifying on the left instead yields the segment type $(0,2k+1,k)$, and compactifying on both sides yields the segment type $(0,2k+1,0)$.

We can now easily build the segment type $(m,2(k+m)+1,m)$ since $(m,2(k+m)+1,m)$↗ = ( $(0,2k+1,0)$↗ ( $L$$L$↗ )$^m$ ).

Finally, we can build the segment type $(i,2k+1,j)$ for any $i,j ≤ k$. $(i,2k+1,j)$↗ can be built by splitting into two internal horizontal bands and crossing those bands using the internal segment sequence ( $(0,2a+1,a)$↗ ( $L$$L$↗ )$^i$ ( $L$$L$↘ )$^j$ $(b,2b+1,0)$↗ ), where $a = k-i$ and $b = k-j$. For ease of understanding, below is an illustration for $(1,9,3)$↗:

(1,9,3)↗ via (0,7,3)↗ ( L↘ L↗ ) ( L↗ L↘ )^3 (1,3,0)↗

We can now easily build a grid-based solution for any finite $S⊆ℕ$ that has maximum $(2k+1)$ for some $k∈ℕ$. If $0∉S$ then use grid-set $ℤ$, otherwise use grid-set $ℕ^+∪\frac1{ℕ^+}$. Let $m_{1..n}$ be the positive members of $S$ in increasing order. Let $a_i = \lfloor \frac12(m_i-1) \rfloor$ and $b_i = \lceil \frac12(m_i-1) \rceil$, and note that $a_i,b_i ≤ k$ since $b_i ≤ \frac12 m_i ≤ k+\frac12$. Then we build the solution as follows:
( ... $(k,2k+1,k)$$(k,2k+1,a_1)$$(b_1,2k+1,a_2)$$(b_2,2k+1,a_3)$↗ ... $(b_n,2k+1,k)$$(k,2k+1,k)$↗ ... ).

We can also build a grid-based solution for any finite $S⊆ℕ$ that has maximum $2k$ for some $k∈ℕ$ such that $0∈S$ and $c∈S$ for some $c∈\{1..k\}$. Simply use the above method to get a solution $g$ for $(S∖\{0\})-1$, and then compactify $g$ on the right, and then add the following on the right:

  • ( $L$↘ ... ) if $c = 1$.
  • ( $(0,2(k-c)+1,0)$$(c-1,2c-1,c-2)$$L$↘ ... ) if $c ≥ 2$.

If we unpack the above method, the compactification would simply replace the ( $(b_n,2k+1,k)$$(k,2k+1,k)$↗ ... ) on the right by ( $(b_n,2k+1,0)$↗ ).

For example, the constructed solution for multiplicity set $S = \{0,3,6,8\}$ would look like this:

Multiplicity set {0,3,6,8} achieved by ( ... (3,7,3)↗ (3,7,0)↗ (1,7,2)↗ (2,7,0)↗ (0,3,0)↗ (2,5,1)↘ L↘ ... )

Conjecture.

Take any $S⊆ℕ$. Then $S$ is constructible (i.e. is a multiplicity set of some continuous function from $ℝ{→}ℝ$) iff one of the following holds:

  1. $S$ has an odd maximum.
  2. $S$ has maximum $2n$ and $\{0,k\}⊆S$ for some $k∈\{1..n\}$.
  3. $S$ has infinitely many odd members.
  4. $S$ is infinite and includes zero.

Semi-proof.

The above construction method for finite sets with odd maximum clearly extends to infinite sets with infinitely many odd members. And to achieve any infinite $S⊆ℕ$ with infinitely many even members including zero, let $c,c'$ be positive even members of $S$ such that $2c ≤ c'$, and compactify a solution for $(S∖\{0\})-1$ on the right and then add ( $(0,c'-2c+1,0)$$(c-1,2c-1,c-2)$$L$↘ ... ) on the right.

However, as of now I cannot find a proof that every infinite constructible set must either have infinitely many odd members or include zero...

$\endgroup$
4
  • $\begingroup$ This is great! Can you clarify how the grid-set $1/\Bbb N^+$ is supposed to work? What is $f(k)$ for negative $k$? Maybe it should be more like $f(k) = \max\{2-k, \frac1k\}$? $\endgroup$
    – Milten
    Jun 3, 2022 at 8:08
  • $\begingroup$ @Milten: Thanks for fixing another typographical error! But I do not understand your question. The grid-set only controls the vertical grid-lines, and $f(k),f(k+1)$ must be on adjacent grid-lines for every $k∈ℤ$. If $f$ has grid-set $1/ℕ^+$ then all the grid-lines are above the real-axis so $f$ is strictly positive. The conditions never distinguish between positive and negative inputs to $f$. $\endgroup$
    – user21820
    Jun 3, 2022 at 9:58
  • $\begingroup$ @user21820 Ahh, right, my mistake on the interpretation. But still, we're gonna run out of grid-lines in one direction, no? Say $f$ is increasing and $f(k)=1$. Then what's $f(k+1)$ supposed to be? Assuming I'm correct that $1/\Bbb N^+ := \{1/n \mid n\in \Bbb N^+\}$? If this is the case, then what about using $\Bbb N^+ \cup 1/\Bbb N^+$ or similar? $\endgroup$
    – Milten
    Jun 3, 2022 at 10:05
  • 1
    $\begingroup$ @Milten: Argh, you are right; I forgot to provide enough lines on the other side! Will fix in a minute. $\endgroup$
    – user21820
    Jun 3, 2022 at 10:06

You must log in to answer this question.

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