Isotone functions, inverse image maps, and principal ideals

Let \(E\) and \(F\) be two partially ordered sets

\(f\in F^E\) is an isotone function when it’s order-compatible/order-preserving.

\(\bigwedge\limits_{e_1,e_2\in E}e_1\leq_{E}e_2\implies f(e_1)\leq_{F} f(e_2)\equiv \bigwedge\limits_{e_1\in E}\bigwedge\limits_{e_1\leq_{E}e_2}f(e_1)\leq_{F} f(e_2)\)

I’ve forgone bounded quantification for indexed conjunction here:
\(\bigwedge\limits_{x\in X}\phi(x)\equiv\forall x (x\in X\implies\phi(x))\). I did that to make some formal deductions below much clearer. It also makes the logic sentences more concise,

For, \(y\in F\), \(\downarrow y\) is the principal down-set of \(F\) generated by \(y\in F\).

\(\downarrow y = \{y^{\prime}\mid y^{\prime}\in F, y^{\prime}\leq_{F} y\}\)

\(E^{\prime}\subseteq E\) is a down-set of \(E\) when it contains all the principal down-sets generated by its members. Downward closure can be expressed in plain set algebra as well: \((\bigcup_{e\in E^{\prime}}\downarrow e)\subseteq E^{\prime}\). And, down-sets are also called ideals.

\(\bigwedge\limits_{e,e^{\prime}\in E}e\in E^{\prime}\land e^{\prime}\leq_{E} e\implies e^{\prime}\in E^{\prime}\equiv \bigwedge\limits_{e\in E^{\prime}} \downarrow e \subseteq E^{\prime} \equiv \bigwedge\limits_{e\in E^{\prime}}\bigwedge\limits_{e^{\prime}\leq_{E} e} e^{\prime}\in E^{\prime}\)

\(f^{\leftarrow}(F^{\prime})\) is the inverse image of \(F^{\prime}\subseteq F\).

\(f^{\leftarrow}(F^{\prime})=\{e\mid e\in E, f(e)\in F^{\prime}\}\)

\(f^{\leftarrow}(\downarrow y)\) is the inverse image of the principal down-set generated by \(y\in F\).

\(f^{\leftarrow}(\downarrow y)=\{e\mid e\in E, f(e)\in \downarrow y\}=\{e\mid e\in E, f(e)\leq_{F} y\}\)

Here's a simple result I’d read earlier this year. These two sentences are equivalent:
\(f\) is isotone.
For all \(y\in F\), \(f^{\leftarrow}(\downarrow y)\) is a down-set of \(E\).

I proved it some time back. I figured that I’d share the proof because I used an interesting inference rule/axiom that's similar to universal elimination. It looks pretty cool when mixed with this quantifier-free logic you see me using presently.

Assume sentence one: \(f\) is isotone. \(e\in f^{\leftarrow}(\downarrow y)\) if and only if \(f(e)\leq_{F}y\). Now, consider another \(e^{\prime}\in E\). Because \(f\) is isotone, if \(e^{\prime}\leq_{E} e\), then \(f(e^{\prime})\leq_F f(e)\). And, because the partial order \(\leq_F\) is transitive, \(f(e^{\prime})\leq_F y\). So, an arbitrarily picked \(e^{\prime}\in E\) is a member of \(f^{\leftarrow}(\downarrow y)\) whenever \(e^{\prime}\leq e\) for all \(e\in f^{\leftarrow}(\downarrow y)\). So, \(f^{\leftarrow}(\downarrow y)\) is a down-set.

What about the converse?

First, express the second sentence as a big conjunction.

\(\bigwedge\limits_{y\in F} \hspace{0.125cm} \bigwedge\limits_{e\in f^{\leftarrow}(\downarrow y)} \hspace{0.125cm} \bigwedge\limits_{e^{\prime}\leq_{E} e} e^{\prime}\in f^{\leftarrow}(\downarrow y)\)

Remember that \(e\in f^{\leftarrow}(\downarrow y)\iff f(e)\leq_F y)\).

\(\bigwedge\limits_{y\in F} \hspace{0.125cm} \bigwedge\limits_{e\in f^{\leftarrow}(\downarrow y)} \hspace{0.125cm} \bigwedge\limits_{e^{\prime}\leq_{E} e} f(e^{\prime})\leq_F y\)

Note that \(X_1\subseteq X_2 \implies \left( \bigwedge\limits_{x\in X_2}\phi(x) \implies \bigwedge\limits_{x\in X_1}\phi(x) \right)\).
And, conveniently, \(\text{range}(f)\subseteq F\).

\(\bigwedge\limits_{y\in \text{range}(f)} \hspace{0.125cm} \bigwedge\limits_{e\in f^{\leftarrow}(\downarrow y)} \hspace{0.125cm} \bigwedge\limits_{e^{\prime}\leq_{E} e} f(e^{\prime})\leq_F y\)

Note that for \(f\in B^{A}\)

\(\bigwedge\limits_{b\in\text{range}(f)}\phi(b)\iff \bigwedge\limits_{a\in\text{domain}(f)}\phi(f(a))\)

That’s because \(\text{range}(f)=\{f(a)\mid a\in\text{domain}(f)\}\)

\(\bigwedge\limits_{x\in E} \hspace{0.125cm} \bigwedge\limits_{e\in f^{\leftarrow}(\downarrow f(x))} \hspace{0.125cm} \bigwedge\limits_{e^{\prime}\leq_{E} e} f(e^{\prime})\leq_F f(x)\)

Recall the definition of \(f^{\leftarrow}\).

\(f^{\leftarrow}(\downarrow y)=\{e\mid e\in E, f(e)\leq_{F} y\}\)

Obviously, \(x\in f^{\leftarrow}(\downarrow f(x))\) because it’s a member of \(E\) and \(f(x)\leq_F f(x)\)

So,

\(\bigwedge\limits_{x\in E} \hspace{0.125cm} \bigwedge\limits_{e\in f^{\leftarrow}(\downarrow f(x))} \hspace{0.125cm} \bigwedge\limits_{e^{\prime}\leq_{E} e}\phi(x,e,e^{\prime})\equiv \bigwedge\limits_{x\in E} \hspace{0.125cm} \bigwedge\limits_{e^{\prime}\leq_{E} x} \phi(x,x,e^{\prime})\)

Notice that this is still essentially an application of the "\(X_1\subseteq X_2\implies\dots\)" rule used earlier.

\(\bigwedge\limits_{x\in E} \hspace{0.125cm} \bigwedge\limits_{e^{\prime}\leq_{E} x} f(e^{\prime})\leq_{F} f(x)\)

Finally, the definition of an isotone function is reached.

Here’s the book’s proof of the converse, roughly:

For all \(x,x^{\prime}\in E\), \(x^{\prime}\in f^{\leftarrow}(\downarrow f(x)) \iff f(x^{\prime})\leq_F f(x)\). So, for all \(x\in E\), \(x\in f^{\leftarrow}(\downarrow f(x))\). Pick some \(x\in E\). Now, pick some \(x^{\prime}\in E\) so that \(x^{\prime}\leq_{E}x\). Because \(f^{\leftarrow}(\downarrow f(x))\) is a down-set (by assumption), \(x^{\prime}\in f^{\leftarrow}(\downarrow f(x))\) as well, which in turn implies that \(f(x^{\prime})\leq f(x)\). So \(f\) is isotone.

I wrote this more as a demonstration of the interesting inference rule. Otherwise, I think the book’s proof is more concise.

Counting the integral points in a 0-1 knapsack polytope

Problem

\(n\in\mathbb{N}\)

\(I = [0,n)\)

\(a\in\mathbb{N}^{I}\)

\(W \in \mathbb{N}\)

\(F(I)=\{J \mid J \subseteq I, \sum_{i \in J}a(i) \leq W\}\)

The problem is counting the set family \(F(I)\), i.e. evaluate \(|F(I)|\).

Solution

\(F(I)\) can be decomposed into a finite union of disjoint sets.

\(F_{w}(I)=\{J \mid J \subseteq I, \sum_{i \in J} a(i) = w\}\)

\(F(I)=\bigcup_{w\in [0,W]} F_{w}(I)\)

\(|F(I)|=\sum_{w\in[0,W]} |F_{w}(I)|\)

\(F(\cdot)\) and \(F_w(\cdot)\) are compatible with respect to the inclusion relation. So, if \(\emptyset \subseteq I_1 \subseteq I_2 \subseteq \dots \subseteq I\), then \(F_w(\emptyset) \subseteq F_w(I_1) \subseteq F_w(I_2)\subseteq\dots\subseteq F_w(I)\) and \(F_w(\emptyset) \subseteq F_w(I_1) \subseteq F_w(I_2)\subseteq\dots\subseteq F_w(I)\).

Let \(I_i=[0,i)\). \(I_0=\emptyset\).

\(w=0\rightarrow |F_{w}(\emptyset)|=|\{\emptyset\}|=1\)

\(w\neq 0 \rightarrow |F_{w}(\emptyset)|=|\emptyset|=0\)

Now, here’s the important relation that makes the decomposition of \(F(I)\) useful. It’s a recurrence.

\(|F_{w}(I_{i+1})|=|F_{\textbf{w}}(I_{i})|+|F_{\textbf{w-a(i)}}( I_{i} )|\)

\(|F(I)|=\sum_{w\in[0,W]} |F_{w}(I)|\)

If you fix the set of indices \(J\subseteq I\), then \(|F_{w}(J)|\) is a total function of w. \(|F_{w}(J)|\) can be expressed as a convolution.

\(|F_w(I)| = |F_w(\emptyset)|* |F_w(\{0\})| * |F_w(\{1\})| *\dots * |F_w(\{n-1\})|\)

You can arrive at this convolution term with generating functions too. There’s a nice signal processing intuition for this: the functions being convolved are essentially linear two-tap unattenuated forward echo filters. And applying the recurrence successively just performs a sparse convolution. Notice that \(|F_{w}(\emptyset)|\) is basically the unit impulse.

I think there’s more counting schemes than this. I’m not surprised since this problem is coupled with many other counting problems in algebra and geometry: for example, the constraint on the set system is that of the 0-1 knapsack problem, and the feasible points for that integer linear program are exactly the characteristic functions/vectors of feasible sets in the set system \(F(I)\).

I thought of another problem for later while solving this one. If \(F(I)\) is an independence system over a finite \(I\), then it’s equal to the union of its maximal elements. How do you count or enumerate those elements?

Also, here’s code for the counting scheme, where the convolutions are computed using the direct method. For sequences with many elements and many repeated elements, a number theoretic transform might be better.

#include<iostream>
#include<vector>
#include<cassert>

int main() {
    int n;
    int W; 
    std::cin >> n;
    std::cin >> W;
    assert(W >= 0);
    std::vector<int> a(n); // sequence a
    int i = 0;
    while (i < n) {
        int a_i;
        std::cin >> a_i;
        assert(a_i >= 0);
        a[i] = a_i;
        i = i + 1;
    }
    std::vector<long long> count_F(W + 1);
    count_F[0] = 1;
    i = 0;
    while (i < n) {
        int w = W;
        while (w >= a[i]) {
            if (w - a[i] >= 0) {
                count_F[w] = count_F[w] + count_F[w - a[i]];
            }
            w = w - 1;
        }
        i = i + 1;
    }
    long long count = 0;
    int w = 0;
    while (w <= W) {
        std::cout << count_F[w] << std::endl;
        count = count + count_F[w];
        w = w + 1;
    }
    std::cout << count << std::endl;
}
    

easy problem tackled with set system decomposition

Here’s an easy discrete optimization problem that many computing students see: "maximum sum subarray".

\(I\) is some finite chain, e.g. \(I=[0,n)\).

Let \(F = \{[a,b] \mid a,b\in I\}\) be the set of intervals in \(I\).

There’s a finite sequence of integers \(s\in\mathbb{Z}^{I}\).

For interval \(J \in F\), let \(f(J)=\sum_{i\in J}s(i)\).

Find \[\max_{J\in F} f(J)\]

solution via set system decomposition

Let \(F_b = \{[a,b]\mid a\in I, a\leq b\}\). \(F_b\) is the set of intervals in \(I\) whose lowest upper bound is b.

\[F = \{[a,b] \mid a,b\in I\} = \{\emptyset\}\cup\{[a,b] \mid a,b\in I,a\leq b\}=\{\emptyset\}\cup\bigcup_{b\in I}F_b\]

If \(b\) is not the maximum element of I, then let \(b + 1\) be the unique element that covers \(b\), i.e. \(b \leq c \leq b + 1\) implies that \(c=b\) or \(c=b+1\)

For \(b,b+1\in I\), \[F_{b+1}=\{J\cup \{b+1\}\mid J\in F_{b}\}\cup\{\{b+1\}\}\]

\(f\) is modular, so

\[\{f(J) \mid J\in F_{b+1}\}=\{f(J)+ f(\{b+1\}) \mid J\in F_{b}\}\cup\{f(\{b+1\})\}\]

\(f(\{b+1\})=s(b+1)\), so

\[\{f(J) \mid J\in F_{b+1}\}=\{f(J)+ s(b+1) \mid J\in F_{b}\}\cup\{s(b+1)\}\]

Recalling the decomposition of \(F\) and the optimization program over it,

\[\max_{J\in F} f(J)=\text{max}(f(\emptyset),\max_{b\in I}\max_{J\in F_b}f(J))\]

Recall the relation between \(F_{b+1}\) and \(F_{b}\)

\[\max_{J\in F_{b+1}}f(J)=\text{max}(\max_{J\in f_b}(f(J)+s(b+1)),s(b+1))\] \[\max_{J\in F_{b+1}}f(J)=\text{max}((\max_{J\in f_b}f(J))+s(b+1),s(b+1))\]

\(\text{max}(x+z,y+z)=\text{max}(x,y)+z\), so

\[\max_{J\in F_{b+1}}f(J)=\text{max}((\max_{J\in F_b}f(J)),0)+s(b+1)\]

This can be followed to a dynamic programming solution over the b axis. It’s very simple, so I’m not going to show code for it.

I’ve seen other "explanations" to this problem that use examples and heuristic thinking, but I don’t like those all that much. I’m happy with what I put together here because it follows a very neat pattern: decompose the set system (feasible set). (2) Put the pieces in relation with another. (3) Exploit the relation. This is more valuable than example churning and "guesswork-ish" dynamic programming relation ansatzes.

Here’s interesting extensions to this problem I thought about. What if \(s\) is an infinite sequence with some regularity condition tacked onto it, e.g. some recurrence holds over it, or it’s periodic. What if \(I\) is not a chain?

Distinct Values Subarrays

\(I\) is an index set: \(I=[0,n) = \{0, 1, \dots, n - 1 \}\)

\([i,j] = \{i,i+1,\dots,j\}\), \(|[i,j]| = j - i + 1\)

\((I, F)\) is a set family: \((I, F)\), \(F = \{[i,j] \mid i,j \in I, i \leq j \} = \cup_{j \in I} \{[i,j] \mid i \in I, i \leq j\}\)

\(|F|=|\cup_{j \in I} \{[i,j] \mid i \in I, i \leq j\}|=\sum_{j \in I}|\{[i,j] \mid i \in I, i \leq j\}|=\sum_{j=0}^{n-1}j+1\)

\(|F|=\binom{n + 1}{2}\)

\(A\) is some finite set: \(A = \{\text{a}, \text{b}, \dots\}\). \(s\) is a sequence over \(A\): \(s \in A^{I}\)

\(F_s\) is the family of index sets corresponding to all subarrays of \(s\) that have distinct elements: \(F_s=\{[i,j] \mid i,j \in I, i \leq j, \land_{i,j \in I, i \neq j} s(i) \neq s(j)\}\).

\(F_s\) is a finite, hereditary (downward-closed) set family, so it equals the union of the ideals of its maximal elements. It's not an independence system though because the empty set is not in \(F_s\) The maximal elements of \(F_s\) are index sets corresponding to distinct subarrays, that are not included in any other index set: these subarrays can't be extended without repeating an element. For example, consider this sequence: \(s\equiv\langle \text{abcbd}\rangle\). The maximal distinct subarrays are \(\langle \text{abc}\rangle\) and \(\langle \text{cbd}\rangle\). The corresponding index sets are \(\{0,1,2\}\) and \(\{2,3,4\}\). \(F_s = I(\{0,1,2\}) \cup I(\{2,3,4\})\).

\(I(X)=\{Y \mid Y \in F_s, Y \subseteq X\}\) is the ideal of \(X\). A "sliding window" algorithm for computing \(|F_s|\) follows from this observation: expand a subarray to find the maximal distinct subarrays and use the inclusion-exclusion principle to count their union: \(|F_s|=|I(J_1)| + |I(J_2)| - |I(J_1) \cap I(J_2)|\). This is easy to implement because only adjacent maximal distinct subarrays overlap.

Distinct Values Subarrays problem on CSES: https://cses.fi/problemset/task/3420/

My solution program: https://cses.fi/paste/10b865ef59bbe20ef6257a/

Here's another solution program that is only different in the way it computes the combinations: https://cses.fi/paste/10b865ef59bbe20ef6257a/

laminar set families, modular set functions, segment trees

For sets \(A,B\), let \(A\dotdiv B=(A-B)\cup(B-A)\) be their symmetric difference.

The set of finite covers of set \(A\) is \[\bigcup_{k\in\mathbb{N}}\{\{A_1,\dots,A_k\}\mid A_i\subseteq A, A_1\cup\dots\cup A_k=A\}\]

The set of finite partitions of set \(A\) is \[\bigcup_{k\in\mathbb{N}}\{\{A_1,\dots,A_k\}\mid A_i\subseteq A, A_1\cup\dots\cup A_k=A_1\dotdiv\dots\dotdiv A_k=A\}\]

For \(A'\subseteq A\), let \(\chi_{A'} \in \{0,1\}^A\) be the characteristic function of set A’.

\[a\in A' \leftrightarrow \chi_{A'}(i)=1\]

Let \(I\) be some finite set.

Consider the set system, \(2^{I}\) and integer set function \(f\in\mathbb{Z}^{2^{I}}\). \(f\) is modular when the following holds

\[f(J_1\cup J_2)+f(J_1\cap J_2)=f(J_1)+f(J_2)\]

Let \(s\in\mathbb{Z}^I\). \(f(J)=\sum_{i\in J}s(i)\) is modular.

segment trees

Let \(I=[0,2^k)\): \(I\) is an interval over the natural numbers.

Let \(S(l,j)=[2^{l}j,2^l(j+1))\). \(S(l,j)\) is a dyadic interval

Now, consider the following family of intervals over \(I=[0,n)\):

\[F = \bigcup_{l \in [0,k]}\{S(l,j)\mid j\in [0,2^{k-l})\}\]

\((F,\subseteq)\) is a laminar set family. Since there’s a unique maximum element, \(F\) is a tree. Sets \(S(l-1,2j)\) and \(S(l-1,2j+1)\) partition \(S(l,j)\).

It follows from modularity of \(f\) and the tree structure of \(F\subseteq 2^{I}\) that:

\[f(S(l,j))=f(S(l-1,2j))+f(S(l-1,2j+1))\]

Consider this algorithm.

Split(\(l, j, J\)):
if \(S(l, j) \cap J=\emptyset\) then
return \(\emptyset\)
if \(S(l, j) \subseteq J\) then
return \(S(l, j)\)
else
return \(Split(l-1, 2j, J) \cup Split(l-1, 2j+1, J)\)

\(Split(k,0,J)\subseteq F\) partitions \(J\)

This can be used to solve problems involving range updates and queries over sequences. Here’s a C++ excerpt from a solution to such a problem. Ignore the "lazy" segment trees.

if (disjoint(c,d,a,b)) {
    return 0;
}
else {
    if (subseteq(c,d,a,b)) {
        return f_S[l][j];
    }
    else {
        long long left = get(lazy1_f_S, lazy2_f_S, f_S, k, l-1,2*j,a,b);
        long long right = get(lazy1_f_S, lazy2_f_S, f_S, k, l-1,2*j+1,a,b);
        return left + right;
    }
}

full solution

A rigorous conversion of natural language to a relational query language

Some time back, I was thinking about the problem of converting natural language to a relational query language, e.g. SQL.

Language models nowadays are not robust estimators, and they struggle to generate complex constructions in formal languages. They're not even fit for performing their own uncertainty quantification either. I think this in part has to do with the choice of parametric forms in language models and the optimization programs used to train them. But, I won't get into that here.

Anyways, how do you convert a natural language query to a relational query from the "noisy" outputs of a language model?

I'd first pose this as a statistical inverse problem: you're basically estimating a partial function from natural language (NL) to  relational query language (SQL, in this case). I'd consider it partial since not all natural language sentences correspond to relational queries. The inverse problem is converting NL to SQL. The forward problem is converting SQL to NL.

Considering the limitations of present language models, I think the forward problem more well-posed than the inverse if you do it in a bottom-up manner. And, that's totally feasible because SQL is inductively defined by a grammar.

Imagine that you have two relations and you know the natural language analogue for both of them. Now, you're asked "what's the natural language analogue of the equijoin of those two relations"? That's way easier for today's language models to solve because it leverages these "language models" native language: natural language!

But, what's the use of solving this "forward problem" if we want to actually solve the inverse problem? Well, given some noisy results of the inverse (e.g. a language model's NL-to-SQL conversions), you can use the less noisy forward results of those outputs, and then measure pairwise consistency/similarity. 

This can be followed to a solution that resembles how the Bayesian line of statistics exploits data generating process (DGP).  Altogether, this basically reduces the difficulty of NL-to-SQL to semantic similarity over natural language (consistency checking step), which is very easy nowadays for natural language models.

You could make this process more rigorous with intermediate DSLs/IRs that have to do with your relational schema just as compilers do.

This whole idea can be followed in some interesting directions, like "generating meaningful views".