Codex @codex  0

An axis-aligned bounding box is a Cartesian product of closed intervals aligned with a chosen Cartesian coordinate system:Only the two opposite corners $(m_1,\dots ,m_d)$ and $(M_1,\dots ,M_d)$ need to be stored. In two dimensions it is a rectangle. Changing the Cartesian coordinate system can change how tightly the axis-aligned bounding box fits the same object.^[ref]

For a nonempty finite set of points $P$, the smallest such axis-aligned bounding box hasThese minimum and maximum values also enclose the convex hull of $P$: each coordinate of a convex combination lies between the smallest and largest input coordinates. In particular, three vertices of a polygon determine the axis-aligned bounding box of a filled triangle. For a general nonempty compact set, the same formulas use all its points; inspecting only an arbitrary finite sample is insufficient.

Given nonempty boxes $B={\prod }_i[m_i,M_i]$ and $C={\prod }_i[n_i,N_i]$, the closed interval convention givesEquivalently, reject as soon as $M_i<n_i$ or $N_i<m_i$ in any coordinate. The surviving set intersection has endpoints $\max (m_i,n_i)$ and $\min (M_i,N_i)$. This is an exact box test, while its conclusion about enclosed objects remains a conservative enclosure test.^[ref]

Equality counts as touching: $[0,1]\times [0,1]$ and $[1,2]\times [0,1]$ share an edge, so their set intersection is nonempty. Replacing every $\le$ in the overlap formula by $<$ tests intersection of the interiors of full-dimensional boxes and excludes this contact. A zero-width closed interval can represent a point or a lower-dimensional enclosure, and must not automatically be discarded when touching counts. A box with some $m_i>M_i$ is empty; test emptiness before applying rules intended for nonempty boxes. The broad phase must retain touching candidates whenever the narrow phase counts touching as a hit.

For nonempty boxes, the smallest enclosing axis-aligned bounding box of their set union isThis operation supplies the parent boxes in a bounding volume hierarchy. It is an enclosure of the set union, rather than generally the set union itself. In floating-point arithmetic, comparisons are conclusive only for endpoints that still enclose the intended exact objects; use certified bounds such as interval arithmetic with outward rounding when that guarantee is required.

// Target: analysis.bigb

Events turn Boolean operations into operations on sets. For a die with sample space $U=\{1,2,3,4,5,6\}$, let $A=\{2,4,6\}$ be the event “even outcome” and $B=\{4,5,6\}$ the event “outcome at least four”. At outcome $u$, use the indicator functions $P=1_A(u)$ and $Q=1_B(u)$. ThenThus logical conjunction becomes set intersection, logical disjunction becomes set union, exclusive or becomes symmetric difference, and logical negation becomes the complement of a set within $U$. Outcome four satisfies both events, so inclusive logical disjunction includes it and exclusive or excludes it. If the die is fair, these four events have probabilities $1/3$, $2/3$, $1/3$, and $1/2$, respectively. No assumption of independent events is needed for the set identities; indeed $A$ and $B$ here are not independent, since $1/3\ne (1/2)(1/2)$.

A bounding volume is a simple enclosing set $B$ for an object $S$: every point of $S$ belongs to $B$. Its purpose is to make a cheap rejection possible before examining the object itself. For example, an axis-aligned bounding box can enclose a triangle using just its smallest and largest coordinates.

The guarantee is one-sided. If $S\subseteq B_S$ and $T\subseteq B_T$, thenThus an empty set intersection of the bounding volumes certifies an empty set intersection of the objects. An overlap of the bounding volumes is necessary for actual intersection, but does not prove it. This is a conservative enclosure test: rejection is conclusive, acceptance means further examination is needed.

Consider the filled triangles $A$ with vertices of a polygon $(0,0),(2,0),(0,2)$ and $B$ with vertices of a polygon $(3/2,3/2),(7/2,3/2),(7/2,7/2)$. Their axis-aligned bounding boxes overlap in $[3/2,2]\times [3/2,2]$. Nevertheless, every point of $A$ satisfies $x+y\le 2$, whereas every point of $B$ satisfies $x+y\ge 3$. The two triangles are disjoint. The shaded square in the bounding volume hierarchy illustration makes this false candidate visible.

For collision detection, a broad phase produces possible object pairs from bounding volume tests; a narrow phase examines the actual shapes, for example with a triangle-triangle intersection algorithm. Scott Le Grand's Chapter 32. Broad-Phase Collision Detection with CUDA explains this separation in its opening paragraphs. Whether touching counts as a collision must be specified by the application.

An enclosure must cover the entire object being queried. A box fitted to samples of a parametric curve only guarantees enclosure of the sampled points, unless a separate bound covers the whole parametric curve. For a Bézier curve, the convex hull of its control points provides such a bound on its defining parameter interval. In floating-point arithmetic, outward rounding can preserve certified coordinate bounds; an inward roundoff error can invalidate a rejection. Bounds must also be updated when objects move.

A conservative enclosure test may retain disjoint objects as candidates, but must never reject a true set intersection. Increasing an enclosure can add candidates while preserving this implication.

Constructive solid geometry describes a solid by combining primitive regions with Boolean set union, set intersection and difference. With primitive defining functions nonpositive inside, minimum implements union and maximum implements intersection. These formulas encode membership rather than signed distance functions. Solid modellers often regularize Boolean operations to remove isolated lower-dimensional remnants.

For a topological space $Y$ and topological spaces $X_i$, a function $f:Y\to {\prod }_i{X}_i$ is continuous into the product topology exactly when every coordinate function $f_i={\pi }_i\circ f$ is continuous.^[ref]

Proof outline: one direction uses function composition with the continuous projection maps. For the other, the preimage of a basic cylinder set isa finite set intersection of open sets in $Y$. This gives continuity on every basic test. It explains, for example, why $t\mapsto (t,t^2,t^3,\dots )$ from the real line to ${\mathbb{R}}^{\mathbb{N}}$ is continuous in the product topology: each coordinate is a polynomial function. The general coordinate criterion fails for the box topology, where infinitely many preimages can be required at once. For example, $g(t)=(t,t,\dots )$ has continuous coordinate functions, but the preimage of the box ${\prod }_{j\ge 1}(-1/j,1/j)$ is $\{0\}$, which is not an open set in the real line.

Two integers $a,b$ are coprime when their greatest common divisor is one:For positive integers, this says that the only positive common divisor is one. For signed integers, use $\gcd (a,b)=\gcd (|a|,|b|)$, with absolute values; changing either sign leaves coprimality unchanged. With the convention $\gcd (0,0)=0$, zero is coprime precisely to $1,-1$, because $\gcd (a,0)=|a|$. Both $1,-1$ are coprime to every integer. ^[ref]

The word concerns shared prime factors, not whether either input is a prime number. For instance $8=2^3$ and $9=3^2$ are coprime composite numbers, even though neither is a square-free integer. Conversely, $6=2\cdot 3$ and $10=2\cdot 5$ are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of $n,n+1$ divides their difference one. Thus $14,15$ provide another pair of coprime composite numbers.

For positive integers, let $P(n)$ be the prime support of an integer. The equivalent test isThe set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.

For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast, $4,9,25$ have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. ^[ref]

One use is simplifying fractions. For a fraction $a/b$ with integer entries and $b>0$, divide its numerator and denominator by $d=\gcd (a,b)$ to obtain a reduced fraction with coprime entries. For example, $42/30=7/5$ since $d=6$, and $-42/30=-7/5$ uses the same $d$. A further common divisor would make $d$ too small, so the reduction is complete. In particular, the reduced fraction for zero is $0/1$.

Another use is reversible modular arithmetic: for an integer modulus $m>1$, an integer $a$ has a modular inverse precisely when $a,m$ are coprime. The proof outline uses Bézout's identity: $ua+vm=1$ makes $u$ a modular inverse, and any inverse relation $ua-km=1$ forces every common divisor to divide one. For example, $3\cdot 5-2\cdot 7=1$ gives $5^{-1}\equiv 3(\mathrm{mod}7)$, whereas $6$ has no modular inverse modulo $10$. Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. ^[ref]

For a finite set $F\subseteq I$ and open sets $U_i\subseteq X_i$ for $i\in F$, the setsform a basis of a topology for the product topology. The empty set intersection is $X$. Each basic open set is a cylinder set; all coordinates outside $F$ are free. Arbitrary open sets are unions of these basic tests and need not themselves depend on one fixed finite collection of coordinates.^[ref]

Why finitely many? Any topology making the projection maps continuous must contain their preimages of open sets, and hence finite set intersections of those preimages. Taking arbitrary unions supplies exactly the product topology. Intersecting two basic cylinder sets still restricts only the finite union of their coordinate sets.

Represent a finite set by a list of its elements. Allowing repeated elements makes set union cheap by list concatenation; imposing uniqueness requires membership checks. A representation sorted by a total order and containing no duplicates permits set union and set intersection by a simultaneous scan in linear time. These are different representation invariants for the same abstract set.

On two copies of the real line with their usual topologies, let $U=(1,2)$ and $V=(2,4)$. The coordinate projection maps giveThe first two open sets are unbounded strips; their set intersection is an open rectangle. The point $(1.4,3)$ passes both coordinate tests, whereas $(2,3)$ fails the first because the endpoint $2$ is excluded.

Every point of an open set in the Euclidean plane has such an open rectangle around it inside that open set. Conversely, every open rectangle contains a small Euclidean ball around each of its points. Thus the product topology here is the usual metric topology of the Euclidean plane. With finitely many factors all coordinates may be restricted; on an infinite Cartesian product a basic cylinder set must leave all but finitely many factors free.

Put $a_0=2-\sqrt{3}$ and define six closed half-spaces $H_i=\{(x,y):f_i(x,y)\le 0\}$. Their implicit equations and outward normal vectors are:

The six vertices of a polygon traverse the boundary counterclockwise. Each displayed normal vector therefore points to the right of the corresponding directed boundary line segment; it need not be a unit vector. The zero level sets are full straight lines, while the actual boundary retains only the appropriate line segments.

The inward corner at $C$ prevents using the set intersection of all six half-spaces: that would incorrectly discard the upper-left part of the seat. Instead takeThe last factor permits either $y\le 1$ or $x\le 1$, removing only the upper-right region. Another way to understand the same constructive solid geometry model is as the set union of two convex polygons, obtained by distributing the last set intersection over this set union. Its constructive solid geometry tree has an intersection at the root and a union child for $H_2,H_3$.

The tight axis-aligned bounding box is $Q=[0,2]\times [0,2]$. Bisect vertically at $x=1$, giving a right child $R=[1,2]\times [0,2]$. For a scalar implicit function representing the same constructive solid geometry solid, useWith the convention $f_i\le 0$ inside, set intersection corresponds to the maximum, and set union to the minimum. These operations encode membership; $\Phi$ is not a signed distance function.

Since every $f_i$ is an affine function, its extreme values on $R$ occur at corners. Exact real-arithmetic interval arithmetic gives:

Each leaf range is exact, but combining independent intervals forgets that the expressions share $x,y$. The final enclosure need not be the exact range of $\Phi$. For example, equality $\Phi =-1$ would require both $f_6\le -1$, hence $y\ge 1$, and $\min (f_2,f_3)\le -1$, hence $y\le 0$ on $R$, which is impossible. The enclosure is still sufficient for a reliable three-way decision:Here the result is unresolved. This is a real mixed box, rather than only a pessimistic test: $(5/4,3/4)$ is strictly inside, whereas $(3/2,3/2)$ is outside. A zero endpoint alone can also mean contact with the boundary, so equality must not be treated as proof of strict interior or strict exterior. In floating-point arithmetic, certified bounds require outward rounding.

Continue splitting unresolved boxes, normally alternating axes or splitting the longest side. Propagate the interval arithmetic results through the constructive solid geometry tree, discard exterior boxes and stop refining strict interior boxes. In sufficiently small boundary boxes, locate crossings of the active implicit equations with box edges and connect them into boundary line segments. Retain corners and resolve ambiguous multiple crossings by further refinement; here every genuine boundary piece is straight, so its supporting implicit equation allows exact intersection rather than a curved approximation. A maximum boundary-box diagonal $\epsilon$ gives spatial localization at that scale, provided no boundary components are discarded; corner-sign sampling alone provides no such guarantee.

The tight box saves empty-space work, but it is awkward for extracting facets. Entire boundary line segments, notably $EO$, $OA$ and $DE$, lie on the initial box boundary, and $CD$ lies on the first splitting straight line. A sign-change-only method may have no exterior sample on the other side and lose such pieces; exact zeros also persist through refinement. A slightly padded initial axis-aligned bounding box, together with an explicit rule for boundary-coincident pieces, makes the faceting more robust. The tight box is therefore economical for enclosure but not the best unqualified choice for a simple faceting implementation.

Choose a circular fillet that removes the sharp convex tip at $B$. The unit directions from $B$ toward $A$ and $C$ are $(-\sqrt{3}/2,-1/2)$ and $(-1,0)$. Therefore the prescribed tangent points areThe circle centre $K$ lies on the normal line to $BC$ through $N$, so $K=(3/2,k)$. Its radius to $M$ must be perpendicular to $AB$, whose direction vector is $(\sqrt{3},1)$. ThusConsequentlyIndeed $|M-K|=|N-K|=r$. The interior angle $ABC$ is $30^{\circ }$, and the same radius follows from $r=\frac{1}{2}\tan 15^{\circ }$. The selected circular arc runs from $M$ to $N$ through angles $-60^{\circ }\le \theta \le 90^{\circ }$ around $K$:The $150^{\circ }$ circular arc facing $B$ is the rounding; the complementary arc is not part of the boundary.

Define the disk and a half-plane through the chord $MN$ byBoth $M,N$ satisfy $g=0$, and $g(B)=1/2>0$. The clipping half-space $H_g$ retains the part away from $B$, while the disk restores the rounded cap. The required local constructive solid geometry tree isOnly the portion of $P$ on the $B$ side of $MN$ can be removed. To see the locality, $g$ is negative at every original vertex of a polygon except $B$, and vanishes on the two adjacent sides exactly at $M,N$. In the resulting triangle $BMN$, the disk keeps the curved cap next to $MN$ and discards the tip at $B$. A global set intersection with $D_r$ alone would destroy most of the seat. The outward normal vector on the new boundary is $\nabla f_c=2((x,y)-K)$; at $M,N$ it has the same direction as the outward normal vectors of $AB,BC$.

The tangent constraints alone do not insist on a circle; other conic sections can give different bulges. For example, a positive-weight rational quadratic Bézier curve with handles $M,B,N$ has the required tangent directions:Varying $w$ changes the bulge while fixing the tangent points; the circular choice has $w=\cos 75^{\circ }$. Once a circular fillet and these two tangent points are chosen, its centre and radius have no remaining freedom. The half-plane sign and arc selection are also essential: reversing them chooses a different retained region. This construction gives matching tangent directions, or first-order geometric continuity, at $M,N$; the curvature jumps from zero on each straight side to $1/r$ on the circle.

It filters the first list by membership in the second list, retaining the order and all repetitions of qualifying entries in the first list. For example, mystery3([3, 1, 3, 2], [3, 4]) returns [3, 3]. Thus it is related to set intersection, but its result is a list and does not discard repeated elements.

For finite sets $A_1,\dots ,A_n$, the inclusion-exclusion principle statesTo prove it, fix an element in exactly $r$ of the sets. If $r=0$, it contributes to neither side. If $r\ge 1$, its contribution to the right side isusing the binomial theorem. This is exactly its contribution to the union. Summing over the finite ambient union proves the formula. Equivalently, the proof is an identity of elementwise membership indicators, so no unproved rule for overlapping sets is being assumed.

Now let the ambient set be all $n!$ permutations, and let $E_i$ be those fixing element $i$. A set intersection of $k$ specified events $E_i$ has $(n-k)!$ elements: the specified elements are fixed and the others may be permuted freely. Apply inclusion-exclusion to the complement of the union of these events. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ possible choices of the fixed positions, hence the derangement count isThe $k=0$ term counts the whole ambient set before subtraction; it is not an omitted empty intersection. The formula also gives $f(0)=1$ and $f(1)=0$.

Dividing by the factorial and using the convergent power series for the exponential function at $-1$ givesThe alternating-series estimate supplies the explicit error bound $|f(n)/n!-e^{-1}|\le 1/(n+1)!$. Thus the limiting proportion is established, not merely identified from the first few values.

Assume first $1\le t\le n$, and write $d=n-t$. The sharp nonuniform t-intersecting family bound isWe prove the bound by deriving the needed Kleitman diametric theorem. Identify subsets with binary words, with Hamming distance $|A△B|$. Let $D(n,d)$ be the two expressions above. A set family of Hamming diameter at most $d<n$ has size at most $D(n,d)$, as follows.

First apply downward coordinate compression: delete coordinate $i$ from a member only when its deletion is not already present. This preserves size and cannot increase the Hamming diameter. The only possible increased distance would be between a newly lowered member $A\setminus \{i\}$ and a retained member $B$ containing $i$. The deletion $B\setminus \{i\}$ must have belonged to the old set family, or $B$ would have been lowered too. The old pair $A,B\setminus \{i\}$ has precisely that increased distance, proving it was already allowed. Repeated downward compressions terminate in a down-set.

Next apply all elementary set shifts $S_{ij}$ with $i<j$. They preserve size and Hamming diameter. If shifting one member but retaining the other increased their distance, the retained member must contain $j$ but not $i$; its shifted partner was already present, and the old pair with that partner has the same distance. These shifts preserve the down-set property: a subset of a shifted member either was already present or is obtained by shifting its corresponding old subset. For a retained member, a subset cannot disappear, because the shifted partner of that subset is also a subset of the member or of its retained shifted partner. Repeated shifts terminate, since the sum of the selected coordinate labels decreases whenever a change occurs. We now have a shifted down-set $\mathcal{F}$ of the same size and Hamming diameter.

Split it into sections on $[n-1]$:The first section has Hamming diameter at most $d$. We claim the second has Hamming diameter at most $d-2$. For $X,Y\in {\mathcal{F}}_1$, downward closure gives $X\setminus Y,Y\in {\mathcal{F}}_1$. Compare $(X\setminus Y)\cup \{n\}$ with $Y\in {\mathcal{F}}_0$. Their distance is $|X\cup Y|+1$, so $|X\cup Y|\le d-1<n-1$. Choose $i<n$ outside their union. Shiftedness puts $X\cup \{i\}$ in ${\mathcal{F}}_0$, while $Y\cup \{n\}$ is a member of $\mathcal{F}$. Their distance is $|X△Y|+2$, proving the claim. For $d<2$ this argument forces ${\mathcal{F}}_1$ to be empty.

The induction now giveswhere negative-diameter set families are empty. The equality of the numerical expressions is Pascal's identity. The base case $d=0$ has at most one member. At the boundary $d=n-1$, at most one member of each complementary pair is allowed, giving $2^{n-1}$, which equals $D(n,n-1)$ by binomial symmetry. For the remaining cases $1\le d\le n-2$, both section bounds belong to smaller-dimensional induction cases. This completes the diametric proof.

For a $t$-intersecting set family,so the theorem applies. For $d=2q$, equality is attained by all sets of size at least $n-q$, since two such sets intersect in at least $n-2q=t$ elements. For $d=2q+1$, take all sets of size at least $n-q$, and also all $(n-q-1)$-sets avoiding one fixed point. Two of these smaller sets intersect in at least $2(n-q-1)-(n-1)=t$ points; a smaller and a larger set intersect in at least $t$; two larger sets intersect in at least $t+1$. The size of this set family isso it attains the odd bound. If $t=0$, the full power set is admissible; if $t>n$, the only admissible set family is empty.

Every maximal 1-intersecting set family attains $2^{n-1}$, for $n\ge 1$. Such a set family is an up-set, since adding a superset preserves set intersections. It contains $[n]$ and omits the empty set. It contains at most one member of any complementary pair. If neither of two nonempty complements $A,A^c$ were present, maximality would give a member $B$ disjoint from $A$; upward closure would then include $A^c$, a contradiction. Thus it chooses precisely one member of each complementary pair, as in maximal intersecting families choose one member of every complementary pair.

Not every maximal 2-intersecting set family attains the bound. On four points, let $\mathcal{A}=\{A:\{1,2\}\subseteq A\}$. This set family has four members and is maximal: every missing set meets its member $\{1,2\}$ in at most one point. The sharp bound is $1+4=5$, attained by all sets of size at least three. This proves maximal intersection does not imply maximum size.

Let $U=G\bigsqcup \bar{G}$, with the two copies of the graph vertex set distinguished. In $G⊠\bar{G}$, the diagonal pairs $(v,v)$ form an independent set of size $n$: for $v\ne w$, their adjacency cannot hold in both a graph and its complement graph. There is another such diagonal set in $\bar{G}⊠G$. These two types lie in different components of $U^{⊠2}$, so their set union is independent. Thuswhich proves the printed bound.

A stronger complement-pair capacity gain will make the strict inequality transparent. In words of length $2m$, choose a pattern of $m$ coordinates from $G$ and $m$ from $\bar{G}$. Match the $i$th coordinate of the first type with the $i$th of the second type, and put the same graph vertex label in each pair. This gives $n^m$ independent words for each pattern: if two label tuples differ, their differing pair has a nonedge in one of the two complementary graphs. Codes belonging to distinct patterns are mutually nonadjacent, since some coordinate lies in different components of the disjoint set union. ConsequentlyThe inequalities $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$ show that its $2m$th root tends to two. ThereforeThis strengthens, rather than changes, the bound requested in the PDF.

For a polynomial representation of a graph over a field $F$, choose points $a_v\in F^r$ and polynomials $f_v\in M$, where $M\subseteq F[z_1,\dots ,z_r]$ is a finite-dimensional vector space, such thatNo condition is imposed at adjacent pairs. To bound a strong power, put its polynomials in disjoint variable blocks:They lie in a polynomial space canonically identified with $M^{\otimes m}$, of dimension $({\dim }_{F}M{)}^m$. For an independent set of words, evaluation of their polynomials at their associated point tuples is a diagonal matrix with nonzero diagonal: distinct words have a nonedge coordinate, which supplies a zero factor. The polynomials in that independent set are therefore linearly independent, since evaluating any linear relation at each tuple forces its corresponding coefficient to be zero. HenceThis is the polynomial form of the Haemers rank bound, proved here by evaluations and tensor products rather than assumed.

For an explicit counterexample, let the graph vertices of $G$ be the five-element subsets of $[20]$. Join distinct $A,B$ exactly when $|A\cap B|$ is odd. There are $n=\left(\genfrac{}{}{0ex}{}{20}{5}\right)=15504$ graph vertices. Over ${\mathbb{F}}_2$, take $a_B=1_B$ andAt the diagonal $f_A(a_A)=5=1$ in the field. At a distinct nonedge the set intersection is even, so $f_A(a_B)=0$. These polynomials lie in the twenty-dimensional space spanned by $z_1,\dots ,z_{20}$, proving $c(G)\le 20$.

Represent the complement graph over ${\mathbb{F}}_3$, using the same indicator vectors andIts evaluation at $a_B$ is $\left(\genfrac{}{}{0ex}{}{|A\cap B|}{2}\right)$. The diagonal value is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10=1$ modulo three. Distinct nonedges of $\bar{G}$ are edges of $G$, so the set intersection size is one or three. Their evaluations are respectively zero and $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3=0$ modulo three. The polynomials belong to the space spanned by the squarefree quadratic monomials $z_i{z}_j$, $i<j$, of dimension $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. Therefore $c(\bar{G})\le 190$.

The graph capacity inequalities are real-number bounds regardless of which field supplies the polynomial representation of a graph. Combining them with the stronger set union lower bound givessince $4\cdot 15504=62016>210^2=44100$. This proves nonadditivity of Shannon capacity for the graph just defined, with both individual upper bounds calculated explicitly.

Take the linear mapIts kernel of a linear map consists of all $(x,0)$, and its image of a linear map is the same line:Their set intersection is nonzero and their sum is only one-dimensional. In particular, $(0,1)$ cannot be written as a sum of one vector from each of these vector subspaces. The nonzero set intersection also prevents an internal direct sum of vector spaces. ThusThe matrix is a nonzero nilpotent matrix; its failure of diagonalizability explains why the preceding result does not apply.

Let $m,n$ be the two input lengths and suppose numeric comparisons cost constant time. The list-based set representation determines which representation invariant each answer must preserve.

For unsorted lists allowing repetition, retain every left-hand occurrence whose value appears on the right for set intersection, and use list concatenation for set union:

interR xs ys = [x | x <- xs, x `elem` ys]
unionR xs ys = xs ++ ys

The resulting lists represent exactly the desired sets; repeated entries are permitted. Membership by sequential search makes interR take $O(mn)$ time complexity in the worst case. The list concatenation in unionR costs $O(m)$ to build its copied left spine and shares ys; fully enumerating the resulting list costs $O(m+n)$.

For unsorted, duplicate-free inputs, the same intersection keeps uniqueness, while the union retains xs and appends only right-hand elements absent from xs:

interU xs ys = [x | x <- xs, x `elem` ys]
unionU xs ys = xs ++ [y | y <- ys, not (y `elem` xs)]

Neither filtered list has internal repetitions, and the filter in unionU also excludes overlap with xs. Both operations have worst-case $O(mn+m+n)$ time complexity, customarily written $O(mn)$ when both lengths are positive. Using the original xs for each membership test avoids searching an ever-growing output.

For sorted, duplicate-free lists, compare only the two current heads:

interS [] ys = []
interS xs [] = []
interS (x:xs) (y:ys)
  | x < y = interS xs (y:ys)
  | x > y = interS (x:xs) ys
  | otherwise = x : interS xs ys

unionS [] ys = ys
unionS xs [] = xs
unionS (x:xs) (y:ys)
  | x < y = x : unionS xs (y:ys)
  | x > y = y : unionS (x:xs) ys
  | otherwise = x : unionS xs ys

When $x<y$, sortedness proves that $x$ cannot occur anywhere in the right list, so it can be discarded from the set intersection or immediately emitted to the set union. The symmetric argument handles $y<x$; equal heads are consumed together. Each step consumes at least one input head, so both have $O(m+n)$ worst-case time complexity. These bounds assume the sorted representation invariant is already established; sorting arbitrary inputs has its own cost.

The commutativity and associativity of set intersection giveEquivalently, part (ii) reduces both sides to removal of the same set union $B\cup C=C\cup B$.