A Blog on Lattices and it's uses

   

 

 

Vishwakarma Institute of Technology

 

Discrete Structures

 

Blog on Lattices

 

Prepared by:

3 Abhishek Dighekar

5 Atharv Bagade

19 Harish Garud

22 Haripriya Arya

 

 

Topics:

 

1. General introduction to Lattices

2. Properties of Lattices

3. Types of Lattices

4. Real life applications of lattices

 

 

1)Introduction to Lattices:

 

A lattice is an abstract structure studied in the mathematical sub-disciplines of order theory and abstract algebra.

Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities.

Lattice theory is based on a single undefined relation, the inclusion relation x^y. In this it resembles group theory, which is based on one undefined operation, group multiplication.

A lattice is a poset in (L,≤) in which every subset {a,b} consisting of two elements has a least upper bound and a greatest lower bound.

LUB({a,b}) is denoted by a v b and is called the join of a and b. GLB({a,b}) is denoted by a Λ b and is called the meet of a and b.

For eg:

 

 

Eg 1) is a lattice.

Eg 2) Is not a lattice because f v g does not exist.

Partially Ordered Set:

 The partially ordered set which consists of all the subsets of X = {1,2,3} under the  relation is called a lattice.

 

 

Figure 1

Every element pair in P(X) has a join as well as a meet. The meet is the intersection of the two subsets while the join of the two subsets is called their Union.

join: {1} V {2} = {1} U {2} = {1, 2};

meet: {1} ^ {2} = {1} ∩ {2} = NULL

The above result can be generalized to any set of n elements, thus the power set P(X) of any set X under the subset ordering ⊆ forms a lattice.

The partially ordered set of all the divisors of 60 which are ordered by their divisibility can also be called a lattice. The set containing the divisors of 60 can be represented as:

D₆₀ = {1,2,3,4,5,6,10,12,15,20,30,60}

Figure 2

The join of any two elements x and y from the above set is their Least Common Multiple(LCM) i.e LCM(x,y) while the meet is their Greatest Common Divisor(GCD) i.e GCD(x.y).

For example:

 join: 12 V 20 = LCM(12,20) = 60

meet: 12 ^ 20 = GCD(12,20) = 4

Partition Lattice of a Four-Element Set:

 

A partition P of set X is a set of non-empty pairwise disjoint subsets X₁, X₂ …. X_n  such that:

· The union of the subsets X_i  in P where 1 ≤ i ≤ n is equal to X.

· P does not contain the empty set NULL

 

· The intersection of any distinct subsets in the partition P is empty

 

 

Figure 3

 

 

2)Properties of Lattices:

A. Idempotent Properties:

a) a v a = a

b) a /\ a = a

B. Commutative Properties:

a) a v b = b v a

b) a /\ b = b /\ a

C. Associative Properties:

a) a v ( b v c ) = ( a v b )  v c

b) a /\ ( b /\ c ) = ( a /\ b ) /\ c

D. Absorption Properties:

a) a v ( a /\ b) = a

b) a /\ ( a v b ) = a

Theorem:

a) a v b = b iff a ≤ b

b) a Λ b =a iff a ≤ b

c) a Λ b =a iff a v b = b

Theorem:

1. If a ≤ b then

a) a v c ≤ b v c

b) a Λ c ≤ b Λ c

2. a ≤ c and b ≤ c iff a v b ≤ c

3. c ≤ a and c ≤ b iff c ≤ a Λ b

4. if a ≤ b and c ≤ d then

a) a v c ≤ b v d

b) a Λ c ≤ b Λ d

 

3) Types of Lattices:

 

1. Isomorphic Lattices:

If f: L1 -> L2 is an isomorphism from the poset (L1,≤1) to the poset (L2,≤2) then L1 is a lattice iff L2 is a lattice.

If a and b are elements of L1 then f(a Λ b) = f(a) Λ f(b) and

f( a v b) = f(a) v f(b)

If two lattices are isomorphic as posets we say they are isomorphic lattices.

2. Complete Lattices
A partially ordered set (L,≼) is called an entire lattice if all its subsets have both a join and a meet. This is often a stronger condition than for a general lattice  where every pair of elements must have a join and a meet.
Any non-empty finite lattice is complete. Among other examples to be mentioned are
* the facility set P(A) of a bunch A ordered by the subset relation ⊆.
* a group of natural numbers N ordered by the divisibility relation "|".

3. Bounded Lattices
A lattice (L,≼) is claimed to be bounded if it's a greatest element and a least element. The foremost effective and least elements are denoted by 1 and 0 respectively.
Let a be any element in L. Then the subsequent identities hold:

0∨a=a∨0=a;

0∧a=a∧0=0;
            1∧a=a∧1=a;

1∨a=a∨1=1.
            It is obvious here that 0≼a≼1.
           Suppose for example, the power set P(A) containing all subsets of A ordered by                the relation ⊆. The only element of the lattice is that the set A itself, and thus the              smallest  element is empty set ∅.

4. Complemented Lattices
Suppose (L,≼) is also a bounded lattice with greatest element 1 and least element 0. Let a,b∈L. part b is termed a complement of a if
a∧b=0 and a∨b=1.
A bounded lattice (L,≼) is claimed to be complemented if every element in L features a complement.
In particular, the complement of 0 is 1, and also the complement of 1 is 0.

Figure 4

                      
        Every element in D30 contains a complement:
        1→30,2→15,3→10,5→6,6→5,10→3,15→2,30→1.
        Indeed, it's easy to work out that
        2∨15=LCM(2,15)=30;

        2∧15=GCD(2,15)=1.
        The same is true for all other elements of D30.
       Note that not all lattices of kind (Dn,|) are complemented. as an example, the lattice         (D20,|) isn't complemented.

5. Distributive Lattices
A lattice (L,≼) is said to be distributive iff for any elements a,b and c in L, the following distributive properties hold:
a∨(b∧c)=(a∨b)∧(a∨c);
a∧(b∨c)=(a∧b)∨(a∧c).
For any set the flexibility set lattice could also be a distributive lattice.
The figure below shows the pentagon lattice and thus the diamond lattice that are samples of non-distributive lattices.

                                                         Figure 5.

6. Modular Lattices
A lattice (L,≼) is called modular if for any elements a,b and c in L the following property is satisfied:
a≼b implies a∨(c∧b)=(a∨c)∧b.
An example of a modular lattice is that the diamond lattice shown above. Consider an example, two comparable elements a and 1, so a≼1. By taking b because the 3rd element, we have
a≼1 implies a∨(b∧1)=(a∨b)∧1.
Calculate the joins and meets:
LHS=a∨(b∧1)=a∨b=1;
RHS=(a∨b)∧1=1∧1=1.
As it could seen, LHS=RHS.

7. Boolean Lattices
A complemented distributive lattice known as a Boolean lattice.
An example of a Boolean lattice is that the flexibility set lattice (P(A),⊆) defined on a set A.
Since a Boolean lattice is complemented,  it contains a greatest element 1 and a least element 0. A  Boolean lattice has two binary operations - join ∨ and meet ∧. Complementation (if it's unique) may be considered a monadic operation denoted by w¯ or c. Given the operational notation, a Boolean lattice is taken into consideration as a proper logic and is denoted by (B,∨,∧,w¯).
The simplest logic is defined on the set of two elements B= and obeys the subsequent rules:
* Join (Boolean addition) operations:
0∨0=0+0=0;
0∨1=0+1=1;
1∨0=1+0=1;
1∨1=1+1=1.
* Meet (Boolean product) operations:
0∧0=0⋅0=0;
0∧1=0⋅1=0;
1∧0=1⋅0=0;
1∧1=1⋅1=1.
* Complementation operations:
0¯=1;
1¯=0.
This simple arithmetic lands up within the subsequent Boolean identities, where a∈{0,1}:

Figure 6

 

 

 

 

 

 

 

 

 

4) Real life applications of Lattices:

 

 

Point lattices are powerful mathematical objects that have been used to efficiently solve many important problems in computer science, most notably in the areas of cryptography and combinatorial optimization. We can also understand the theory of point lattices, their algorithms, and a selection of applications of lattices to both cryptography and other areas of computer science, mathematics, and communication theory. Besides the best currently known algorithms it is also used to solve the most important lattice problems (both in their exact and approximate versions), we will touch several related areas:

· Combinatorial Optimization: The asymptotically fastest Integer Programming algorithm known to date is based on lattices.

· Cryptography: Lattices have been used to design a wide range of cryptographic primitives, including public key encryption, digital signatures, encryption resistant to key leakage attacks, identity based encryption, and fully homomorphic encryption.

· Complexity: Cryptographic applications of lattices have been in large part stimulated by a connection between the average-case and worst-case complexity of lattice problems that is very interesting on its own.

· Harmonic Analysis: n-dimensional Fourier analysis is one of the most powerful tools currently used in the study of lattices, both in algorithms, complexity and mathematics.

· Algebraic Number Theory: Lattices have been used to algorithmically solve many problems in algebraic number theory, and algebraic number theory is an imporant tool in the design of several lattices with special properties that turn out to be very useful in applications.