What does "modular" in "modular functions" mean?

Question

From Wikipedia

If $\Omega$ is a set, a submodular function is a set function $f:2^{\Omega}\rightarrow \mathbb{R}$, where $2^\Omega$ denotes the power set of $\Omega$, which satisfies one of the following equivalent definitions.

• For every $X, Y \subseteq \Omega$ with $ X \subseteq Y$ and every $x \in \Omega \backslash Y$ we have that $f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)$.
• For every $S, T \subseteq \Omega$ we have that $f(S)+f(T)\geq f(S\cup T)+f(S\cap T$).
• For every $X\subseteq \Omega $ and $x_1,x_2\in \Omega\backslash X$ we have that $f(X\cup \{x_1\})+f(X\cup \{x_2\})\geq f(X\cup \{x_1,x_2\})+f(X)$.

I wonder what "modular" mean in the concept name "submodular functions"? Is it related to other meanings of "modular"in mathematics (e.g. modular arithmetic).

Thanks!

Answer 1

I just stumbled into this question. Although Malik's correctly points out what modular functions are in complex analysis, the definition of a "modular" function in optimization is missing and has a completely different meaning in this context.

If $\Omega$ is a finite set, a modular set function $f \colon 2^{\Omega} \rightarrow \mathbb{R}$ is a function that satisfies the following condition, $$ f(S) = \sum_{e \in S} f(e) \quad \forall S \subseteq \Omega,$$

So it just means that the function is linear. By definition, every modular set function is a submodular function. The term "sub-" probably comes from the analog between submodular functions and discrete concave function.

Answer 2

I personally don't know what is the meaning of a submodular function in optimization (except what wikipedia gives me as a definition). However, "modular functions" are beautiful objects you can find in complex analysis. They are related to something we call the modular group denoted $\Gamma$. Basically, modular functions are complex meromorphic functions (meromorphic means that they have countably many singularities in the complex plane, those are called poles and at these points, your function blows up !) with some period $T$ (they thus have a fourier expansion !) and are invariant under the action of the modular group. What we mean by invariant is that if you take a matrix $A\in\Gamma$, then $f(A\tau)=f(\tau)$. Such functions play a very important role in number theory and are used for example to prove one of the most remarkable formula in mathematics :

${\displaystyle p(n)={\frac {1}{2\pi {\sqrt {2}}}}\sum _{k=1}^{v}A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\exp \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right)}$

It is called the partition function.

Answer 3

Let $f: 2^P \to \mathbb{R}$ (where $P$ is a ground set of elements), $A \subseteq B \subseteq P$ and $e \in P \setminus B$

A submodular function is one that satisfies

$$ f(A \cup {e}) - f(A) \geq f(B \cup {e}) - f(B)$$

A supermodular function is one that satisfies

$$ f(A \cup {e}) - f(A) \leq f(B \cup {e}) - f(B)$$

A modular function is the one that is both submodular and supermodular. That is,

$$ f(A \cup {e}) - f(A) = f(B \cup {e}) - f(B)$$

Using induction we can mathematically show that any modular function can be decomposed as

$$m(A) = m(\emptyset) + \sum_{a \in A}m(a)$$

Thus this summation of evaluation at individual points $a$ gives rise to the "modularity" term.

PS: One of the previous answers decomposed modular function merely as summation, but it can have an offset as well.