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

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.