text:
# The story of two lovers and the beauty of statistics

[The original title for this post was “The story of two lovers, joint densities and the beauty of statistics”. I dropped the “joint densities” from the title]

Recently a friend of mine gave me a puzzle. The puzzle is as follows:

Many years ago there were two people, secretly in love, and were traveling with a group of friends who did not know they are in love. The large group of friends were going around Europe by bus. Stopping in major cities and staying in hotels. In the long hallway of hotels, every person would get a separate room. Every night one of these lovers would sneak out of their room and go to the other’s room for an innocent cuddling. The puzzle is: if the long hallway is L meters long and rooms are uniformly spread along the hallway. What would be the average length that one of them needs to tiptoe to reach the other one.

Depending on how you want to solve this problem this can be an easy or a relatively hard problem. We will solve it two ways. First we can solve it with simulation and next we can validate the simulation with an analytical solution.

Let’s first simplify the problem. Assume the location of one of them is $X \sim U(0,L)$ and the other is located at $Y \sim U(0,L)$. We want to find the average value for \$latex Z= |X-Y|

And the histogram of $Z$ values is shown below. $Z$ is following a triangular distribution.

If R is your favorite language then you might find the rgl and akima libraries pretty useful here. You can produce visualizations of Z values (vs X and Y) using R.

This problem can be solved in 6 lines of python or R (perhaps two line if you don’t mind a compressed notation). But can how can we find a closed form solution for this?

Analytical solution
We have $X \sim U(0,L)$ and $Y \sim U(0,L)$. We want to find the average value for $E[Z]= E[|X-Y|]$. Additionally we know that $Y$ and $X$ are independent $X \perp Y$. The probability density function for $X$ and $Y$ are $f_X(x) = 1/L$ and $f_Y(y) = 1/L$. Since the two variables are independent then the expectation of the joint probability is in the form of:

$E[Z] = \int_0^L \int_0^L |x-y|f_X(x)f_Y(y)dy dx$

By replacing $f_X(x) = 1/L$ and $f_Y(y) = 1/L$ we have:

$E[Z] = \int_0^L \int_0^L |x-y| \frac{1}{L^2} dy dx$

We can now remove the absolute value by conditioning on the value of $X-Y$. Meaning, if $X-Y>0$ then $|X-Y| = X-Y$ otherwise $|X-Y| = Y-X$.

$E[Z] = \frac{1}{L^2} \int_0^L \int_0^x (x-y) dy dx + \int_0^L \int_x^L (y-x) dy dx$

Therefore:

$E[Z] = \frac{1}{L^2} \int_0^L (xy-1/2y^2)_{y=0}^{y=x} dx + \int_0^L (1/2y^2-xy)_{y=x}^{y=L} dx$

This is equal to $\frac{1}{3} L$. So the two lovers would, on average, walk one third of the hallway to see each other.

# Python Tips: Converting a string to a list of characters

Sometimes you may need to convert a string to a list of characters (for example you may want to calculate a hash value of the string using the folding method). If you want to break the string on spaces then you can simply use  mystring.split() . For splitting the string into individual characters you can simply use  list(mystring) .

However, in practice we almost never build our own hash function. Python has a default hash() function. For cryptography you might use the  Hashlib module though.

# Interesting questions: Anagram Numbers

I found this old question in the archives of the British informatics olympiads

Question 1: Anagram Numbers
An anagram number is a number that can be multiplied by at least one single digit number (other than 1) to become an anagram of itself. Any anagrams formed by multiplying an anagram number by a digit are said to be generated by that anagram number. Two numbers are anagrams of each other if they can both be formed by rearranging the same combination of digits.

For example:

• 1246878 is an anagram number; multiplying by 6 generates 7481268 or by 7 generates 8728146. These numbers all contain a single 1, 2, 4, 6, 7 and two 8s.
• 1246879 is not an anagram number.

1(a) [ 25 marks ]

Write a program which reads in a single number (between 1 and 123456789 inclusive) and determines if it is an anagram number. If the number is not an anagram number you should output the word NO. If it is an anagram number you should output each single digit it can be multiplied by to make an anagram of itself.

• Sample run 1
123456789
2 4 5 7 8
• Sample run 2
100
NO

1(b) [ 2 marks ]

85247910 is generated by which anagram numbers?
1(c) [ 3 marks ]
How many anagram numbers between 100,000 and 999,999 contain no duplicated digits?

Here is a quick solution to this program. I am wondering if there is any solution to this that is more efficient?

Results

# Python Basics – A quick python review

I have been working with Python since 2007 on various projects. I have mostly used it on prototyping projects, some web development and some data analysis work. Python has changed a lot. However I still need to sometimes go and review the basics. Here are some useful notes that I have taken over many years. In case you also like to remind yourself of some of the basic operations and techniques in Python these might come in handy. I am also interested to know some of the simple Python principles and techniques that you find useful

Python Variables

For deleting a variable you can use delete

Python style guide uses underscores for specific purposes _ is used for a throw away variable or for referring to the previous results in the interactive Python. Leading __var__ are usually used for reserved variables. Leading single underscore is usually used for internal variables _var.

Keys in Dictionaries
Python has a very easy to use dictionary data structure. Dictionaries are highly efficient that provide O(1) insertion and read operations (as opposed to O(n) in a list). However, it is very easy to accidentally degrade your dictionary to a list and dramatically impact its efficiency. Let’s assume you like to check to know whether your dictionary contains a key. There are two ways to do that. The first method is checking key in dict and the second one is key in dict.keys(). Both will return the correct value. However, the second method is dramatically slower than the first since dict.keys() is in fact a list and not a dictionary anymore

IF Statements

Unlike other programing languages there is no multi branching in Python (no “case” and “switch” statements). Python also uses “elif” for else if

Various Assignment Operations

Zip and Map

Zip and Map are two of the most useful functions in Python. Zip allows you to make tuples of data from lists. Map allows you to apply functions to tuples.

You can define your own function by using lambda. Below is the same sum function

Python Classes

In Python the __init__ method is called automatically at the instantiation stage. Every time Python instantiates an object it will call this method.

List Comprehensions in Python
List comprehensions are one of the most elegant language constructs in Python. Let’s assume we want to produce a list of all numbers between 0 and 100 that are divisible by both 5 and 3. This can be done by the following code

List Slicing in Python
Python has excellent syntaxt for working with its lists. Lists in Python are all zero-indexed so the first element of a list a = [1,2,3] can be found by a[0]. You can also take a range of elements, for example if you like to take the second element all the way to the end you would use a[1:]. Interestingly if you like to take the second element until the end but excluding the last element you would use a[1:-1]. List slicing notation also accepts steps, for example if you like to take the former list but slip every other element, the you would use a[1:-1:2]. You can also use negative steps. See this link for more.

The following code sample allows you to generate bigrams for a sentence

Object Serialization in Python
Python has two modules for serialization cPickle and Marshal. You can compress each serialized object by using the gzip module.

Raising an Exception in Python
If you like to manually raise an arbitrary exception then you can do the following


text:
# Equilibrium Constant

The equilibrium constant is a number which depends on the reaction and the temperature of the reaction mixture when equilibrium is attained. An equilibrium constant of 1 means that both sides are equally popular. The equilibrium constant is:. Chemical Equilibrium: Finding a Constant, K c The purpose of this lab is to experimentally determine the equilibrium constant, K c , for the following chemical reaction: When Fe 3+ and SCN - are combined, equilibrium is established between these two ions and the FeSCN 2+ ion. Rapid Equilibrium Assumption: - enzyme E (macromolecule) and substrate S (ligand) concentrations can be determined using the dissociation constant since E, S, and ES are in rapid equilibrium, as we previously used in our derivation of the equations for facilitated transport. What is the oxidation number of iron in FeSCN+2? 2. Equilibrium chemistry is concerned with systems in chemical equilibrium. The Equilibrium Constant Calculator an online tool which shows Equilibrium Constant for the given input. , the dissociation reaction of water molecule and k 2 is the rate constant for the backward reaction, i. a) Write the expression for the equilibrium constant, Kp, for the reaction. 200 M [H2] = 0. Determine the concentration of all species at equilibrium. I-KI system in aqueous medium at different temperatures. Some politically correct biochemists use kJ/mol rather than kcal/mol. Determination of the Equilibrium Constant Kyle Miller December 11, 2006 1 Purpose The purpose of this experiment is to determine the equilibrium constant for the reaction Fe3+ + SCN− FeSCN2+ and to see if the constant is indeed the same under diﬀerent conditions. Equilibrium Constants th (Reference: 17. The equilibrium constant expression for the reaction is Kc = [HI]2 [H2][I2] Substituting the equilibrium concentrations into the equilibrium expression, Kc = (0. 00 M and [SO3] = 10. When you are doing more complicated calculations, it helps to draw up a RICE table (shown in next lesson). K eq is only used when a reaction is in equilibrium. This means that the equilibrium favors the products of the reaction. The equilibrium constant for the following reaction is 600(C is 4. An equilibrium constant gives a numerical representation of the position of an equilibrium. If the temperature changes, the value of the equilibrium constant also changes. The estimation of the antagonist equilibrium dissociation constant by the Schild plot is based on the assumption that when the same magnitude response is produced by an agonist in presense and absence of an antagonist then the following relationship holds:. eq2] for Equation (2) was calculated from the simulated equilibrium composition for the OS ash-water model systems (Fig. 34 moles each of Brp (g) and C12 (g) are introduced in a container which has a volume Of 11. You can enter your chemical equation in this Partial pressure calculator and submit to know the balanced equation. Introduction A. Equilibrium Brewery - 22-28 Henry Street Suite 1, Middletown, Orange County, New York 10940 - Rated 4. A reaction that has a large equilibrium constant has _____? A) a faster reaction rate than a reaction with a small equilibrium constant. The Equilibrium Constant Calculator an online tool which shows Equilibrium Constant for the given input. The solubility product constant is an equilibrium constant used in solubility equilibrium. The equilibrium constant for the reaction between NO and O 2 to form NO 2 is much larger than 1 (K c = 3 x 10 6). Different reactions have different equilibria. In addition, the smaller the pKa value, the stronger the acid. Their value of the enthalpy is exactly. 000355 Atmosphere. The magnitude of the equilibrium constant, K, indicates the extent to which a reaction will proceed: If K is a large number, it means that the equilibrium concentration of the products is large. Equilibrium constants can also be expressed in terms of pressure. The equilibrium constant [K. Equilibrium: Stable or Unstable? Equilibrium is a state of a system which does not change. The reaction may be spontaneous,in which case the reactants would continue to react until they are exhausted with the end composition being nearly all product. Therefore, thermal equilibrium is attained. The equilibrium constant of this reaction is greater than 1. The equilibrium constant of a chemical reaction is the value of its reaction quotient at chemical equilibrium, a state approached by a dynamic chemical system after sufficient time has elapsed at which its composition has no tendency towards further change. represent the equilibrium constants for reactions being added together, and K' represents the equilibrium constant for the desired reaction. The equilibrium constant, K c, is the value obtained for the equlibrium-constant expression when equilibrium concentrations are substituted. concentration of products. Over a large range of parameters, therefore, it is a very good approximation to view the thermodynamic processes as consisting of such a succession of equilibrium states, which we can chart. Some are so weighed equilibrium constant homework help down with other coursework or real work that they do not have time to write a great essay. The equilibrium constant is a ratio of the concentration of the products raised to the appropriate powers to the concentration of the reactants raised to the appropriate powers. From a graph of concentration as a function of time, students should be able to identify when a system has reached equilibrium. Worked Example: Predict the Value for an Equilibrium Constant, K, at a Different Temperature. , CO2 in water). 930 x 10 CO(g) H200g) CO2 (g) H2(g) K2 5. The equilibrium constant, K, expresses the relationship between products and reactants of a reaction at equilibrium with respect to a specific unit. In the experiment, known amounts of the reactants Fe 3 + and SCN - (thiocyanate ion) will be allowed to react to form the product FeSCN 2 +. 4 mole of hydrogen, 0. Any coefficients in the balanced reaction become the exponents in the equilibrium constant. Experimental observations therefore reveal the criteria for maintaining a system in equilibrium (assuming the system has the potential to reach equilibrium as opposed to going to completion): constant temperature and a closed system. The equilibrium constant of dimerization in heavy water vapor is shown to exceed that in light water vapor within the whole temperature interval. The conversion is. Knowledge of the equilibrium constant for the dominant isotopic species can then be used to calculate the individual isotope equilibrium constants. Part B: The Equilibrium Constant In the second series of reactions, neither Fe3+ (aq) nor SCN − (aq) will be present in vast excess. I-KI system in aqueous medium at different temperatures. For example, the Ka constant for acetic acid (CH 3 COOH) is 0. Acid-base concepts and the Henderson-Hasselbalch equation 314 J/mol K), and K is the equilibrium constant for the folding/unfolding reaction. We have used two levels (+ and -) of binary vapor-liquid equilibrium data and chemical equilibrium constant to evaluate the influence of data on the model representation of the quaternary reactive mixture. These authors used the values of the rate constants at 298K and a calculated value of the entropy change to get a third law value of the equilibrium constant. At Equilibrium : Reaction is proceeding in both directions at the same rate. To determine the equilibrium constant you must consider the chemical reaction written in the form: $aA + bB \rightleftharpoons cC + dD$ The equilibrium constant is defined as:. The chemical equilibrium constant is a numeric value that shows us the extent to which a particular reaction is carried out. Their value of the enthalpy is exactly. Solubility equilibrium is the equilibrium associated with dissolving solids in water to form aqueous solutions. A reaction that has a large equilibrium constant has _____? A) a faster reaction rate than a reaction with a small equilibrium constant. For the general equilibrium equation: aA + bB cC + dD. If the temperature changes, the value of the equilibrium constant also changes. If the value of the equilibrium constant is known, the value of x can be. The value of the equilibrium constant is the reciprocal of. The concentrations of A and B decrease until they reach. asked by Raskin on March 18, 2012; Chemistory. equilibrium constant? We can use our knowledge of LeChatelier's principle to determine how to force the equilibrium position essentially to completion, so that the stoichiometry of the reaction alone can be used to find the concentrations of FeNCS 2+. The equilibrium constant for this reaction, called the water dissociation constant, K w, is 1. Despite the failure of this derivation, the equilibrium constant for a reaction is indeed a constant, independent of the activities of the various species involved, though it. The resulting K can be used to predict other equilibrium positions. bautista department of mining, metallurgical and material engineering , college of engineering university of the philippines, diliman , quezon city, philippines date performed: january 14, 2014 instructor ’s name : mr. a) fixed number of adsorption sites; at equilibrium, at any temperature and gas pressure a fraction of the surface sites θ is occupied by adsorbed molecules, and the fraction 1-θ is free. However, in the absence of an enzyme the reaction could take more than an hour to approach this equilibrium, whereas in the presence of an enzyme, equilibrium could be attained within a. K eq is a general term for equilibrium constant. A reaction that has a large equilibrium constant has _____? A) a faster reaction rate than a reaction with a small equilibrium constant. In a chemical reaction, the equilibrium constant is the value of the reaction quotient when the reaction has reached the equilibrium. This reaction, studied in 1862 by others, was carried out many times with different starting. 4 mole of hydrogen, 0. Click here to view some great books which can aid your learning. If explains how to calculate the equilibrium constant k for a new reaction by changing another reaction. 8: Phosgene, COCl 2, forms from CO and Cl 2 according to the equilibrium CO(g) + Cl 2 (g) COCl 2 (g) At 600 C, a gas mixture of CO and Cl 2 is prepared that has initial partial. Equilibrium constant is the value of the reaction quotient when the reaction has reached equilibrium. The equilibrium constant of a chemical reaction is the value of its reaction quotient at chemical equilibrium, a state approached by a dynamic chemical system after sufficient time has elapsed at which its composition has no tendency towards further change. Chemical Equilibrium Consider a reversible reaction taking place at constant temperature: aA + bB cC + dD The reactantsA and B combine to form productsC and D. Acid-base concepts and the Henderson-Hasselbalch equation 314 J/mol K), and K is the equilibrium constant for the folding/unfolding reaction. Last update: 10-31-2019. the bigger ok is, the greater products are favored, as concentrations of things far exceed that of reactants at equilibrium. Relevant for high school and university chemistry education. 000928 mol O 2 and 1. Set up a table for displaying the initial pressures, the changes in pressure, and the equilibrium pressures. Other Forms • A ‘solubility constant’ is an equilibrium constant. In this experiment we will study the equilibrium properties of the reaction between iron (III) ion, Fe3+,. In the program, we obtain equilibrium constants, compressibility factors, molar volumes and densities using the Soave-Redlich-Kwong equation of state. We can deduce the following: the higher the equilibrium constant is above 1, the greater the concentration of B relative to A. The equilibrium favors products (product concentration is higher than reactant concentration) this favors the forward reaction Equilibrium Constant relates to the number of reactants and products. Rearranging this equation, one can easily get that the equilibrium constant is. @K You are assuming constant pressure in your ideal gas law calculations, which may or may not be true for this question. Thus temperature, T (K), affects the equilibrium constant, and thus the ratio of products to reactants. Worked Example: Predict the Value for an Equilibrium Constant, K, at a Different Temperature. State the conditions for equilibrium and apply them to simple problems. 5 - Determination of an Equilibrium Constant 1 _____University of Puget Sound Department of Chemistry Chem 230 EXP. 29 M What is the equilibrium constant of this reaction?. One of the most common causes of feeling like your equilibrium is off is labrynthitis or vestibulitis, inflammation of the inner ear. Equilibrium Constant Expression For a Reaction The equilibrium constant expression describes the concentration of products divided by the concentration of reactants when the reaction reaches equilibrium. In the experiment, known amounts of the reactants Fe 3 + and SCN - (thiocyanate ion) will be allowed to react to form the product FeSCN 2 +. However, in this calculator, we assume that there is a maximum of two main reactants and two main products. 5 How to Solve Equilibrium Problems. Physical Constants Units of Measure Physical Quantities SI Prefixes Ring Index General Formulae Exact Formulae Source Documents Terms by IUPAC Div. A general formula and corresponding equilibrium. Despite the failure of this derivation, the equilibrium constant for a reaction is indeed a constant, independent of the activities of the various species involved, though it. Definition of equilibrium constant in the AudioEnglish. Rinse the cuvet thoroughly with deionized water, and then fill it to the horizontal line with deionized water. State and apply the relation between force and torque. Meaning of equilibrium constant. Determining Equilibrium Constant for Thiocyanatoiron. Chemical Equilibrium Constants. Calculate Ecell for a cell made up of Sr/Sr2+ and Mg/Mg2+ half cells. The square [ ] brackets indicate the concentration of the chemical species. What is 'Economic Equilibrium '. 000928 mol O 2 and 1. 314 J mol-1 K-1. Experimental Procedure. The equilibrium constant (K s ′) for this reaction (the mathematical quantity that expresses the relationships between the concentrations of the various species present at equilibrium) would normally be given by the equation K s ′ = [SH 2 +] [S −]/[SH] 2, in which the square brackets denote the concentrations of the species…. The equilibrium constant, K, for a chemical system is the ratio of product concentrations to reactant concentrations at equilibrium, each raised to the power of their respective stoichiometric coefficients. Experiment 23 Equilibrium Constant General Chemistry Lab 163-05 February 22, 2011 Prelab Report Subscribe to view the full document. At equilibrium, the expenditures of the forward and opposite reactions would be the comparable. Reversible reactions occur in both directions, but every reversible reaction settles down to an "equilibrium" position. In this case, however, the number of moles of each substance at equilibrium may be used instead of concentration. 29 M What is the equilibrium constant of this reaction?. Enjoy the videos and music you love, upload original content, and share it all with friends, family, and the world on YouTube. Different reactions have different equilibria. To understand equilibrium, you have to realize that both forward and reverse reactions are always taking place at the same time. In addition, the equilibrium constant expression is nothing but the quotient of concentrations of products and concentrations of reactants. 5 M in dilute solutions and is not included in the expression for K. At equilibrium this ratio is equal to the equilibrium constant, K. John Kitchin. These variables include the ones discussed in class such as pressure and temperature. It can be calculated if the equilibrium concentration of each reactant and product in a reaction at equilibrium is known. We find the same results as those given by Henley and Seader in Equilibrium-Stage Separation Operations in Chemical Engineering, Wiley, 1981 (example 4-10 page 175). remember that the ok cost is a ratio of concentrations of things (raised to suitable exponents) OVER REACTANTS (likewise raised to suited exponents. at the same time as those 2 expenditures are equivalent at equilibrium, the concentration of C heavily isn't the comparable because of the fact. If two or more reactions are added to give another, the equilibrium constant for the reaction is the product of the equilibrium constants of the equations added. Get help with your Equilibrium constant homework. The equilibrium law states that the concentrations of the products multiplied together, divided by the concentration of the reactants multiplied together, equal an equilibrium constant (K). The equilibrium constants for the formation of hydrates of acetaldehyde and chloroacetaldehyde are 1 and 37, respectively. When writing the equilibrium expression for a reaction, remember that the products are on the top of the expression and the reactants are on the bottom. It accepts hydrogen ions from H₂O to yield ammonium and hydroxide ions. Is the reaction exothermic or endothermic? Increasing the temperature of the reaction container is the same as adding heat to the reaction system. Rinse the cuvet thoroughly with deionized water, and then fill it to the horizontal line with deionized water. txt) or read online for free. The equilibrium constant is:. Chemical Equilibrium Calculation This spreadsheet will calculate the chemical equilibrium state of an ideal gas mixture, subject to necessary constraints on two intrinsic variables. The greater the heat evolved or used in the reaction, the greater the effect of temperature change on the equilibrium. Enjoy the videos and music you love, upload original content, and share it all with friends, family, and the world on YouTube. Determine the concentration of all species at equilibrium. , the dissociation reaction of water molecule and k 2 is the rate constant for the backward reaction, i. Any dynamic equilibrium can be described in terms of its equilibrium constant, Kc. The equilibrium reaction OH + HNO 3 {} H 2 O + NO 3 was investigated by pulse radiolysis in aqueous solutions. Equilibrium solutions in which solutions that start “near” them move away from the equilibrium solution are called unstable equilibrium points or unstable equilibrium solutions. Objective The purpose of this lab is to observe a reaction in chemical equilibrium changes with the addition of reactants and products, and how to calculate the equilibrium constant with a given equation. Did You Know?. According to Le Chatelier's Principle, the position of equilibrium moves in such a way as to tend to undo the change that you have made. 3: Spectrophotometric determination of equilibrium constant of. I regret that Gaseq is no longer being maintained. Equilibrium Constant Determination INTRODUCTION Every chemical reaction has a characteristic condition of equilibrium at a given temperature. Initially, two moles of CO and one mole of H2O were mixed in a 1. The square [ ] brackets indicate the concentration of the chemical species. Some advice: your teacher may insist on putting units on the equilibrium constant. So, as you speculated, whether or not water is considered in the equilibrium constant entirely depends on whether or not water is a product and if water is the solvent. But the balance exists also between the concentrations of the reactants and products. This section is fairly straightforward and just requires the student to appreciate the relationship between the actual values of the equilibrium constant Kc and the extent of the reaction. Other websites. For a given reaction, at some specified condition of temperature and pressure, the ratio of the amounts of products and reactants present at equilibrium, each raised to their respective powers, is a constant, designated the equilibrium constant of the reaction and represented by the symbol K. The equilibrium constant is defined by equation as −∆ = RT G K exp rxn (9) for the stoichiometry given by equation 1 the equilibrium constant is defined in terms of activities as EB styrene H a a a K = 2 (10). If you change the temperature of a reaction, then Kc also changes. For the reaction ; the equilibrium constant is described by: This is called the Law of Mass Action. To determine the equilibrium constant you must consider the chemical reaction written in the form: $aA + bB \rightleftharpoons cC + dD$ The equilibrium constant is defined as:. the bigger ok is, the greater products are favored, as concentrations of things far exceed that of reactants at equilibrium. The position of equilibrium is changed if you change the concentration of something present in the mixture. b) all sorption sites are uniform (i. The magnitude of an equilibrium constant is a measure of the yield of a reaction when it reaches equilibrium. For dinitrogen tetroxide, which contains nitrogen (N) and oxygen, the chemical reaction is written N 2 O 4 ⇆ 2 NO 2. reaction rate: How fast or slowly a reaction takes place. Some politically correct biochemists use kJ/mol rather than kcal/mol. Any coefficients in the balanced reaction become the exponents in the equilibrium constant. If the dynamics of a system is described by a differential equation (or a system of differential equations), then equilibria can be estimated by setting a derivative (all derivatives) to zero. equilibrium constant can be abbreviated as K What is K abbreviation? One of the meanings of K is "equilibrium constant" What is the abbreviation for equilibrium constant?. 000355 Atmosphere. What happens if we want to find out equilibrium constant of the reverse reaction?. the balanced equation for the reaction system, including the physical states of each species. The equilibrium constant is defined by equation as −∆ = RT G K exp rxn (9) for the stoichiometry given by equation 1 the equilibrium constant is defined in terms of activities as EB styrene H a a a K = 2 (10). A reaction that has a large equilibrium constant has _____? A) a faster reaction rate than a reaction with a small equilibrium constant. This condition is expressed in the equilibrium constant Kc for the reaction. At equilibrium this ratio is equal to the equilibrium constant, K. H3PO4 + 3 H2O 3H3O+ + PO43-Note the water in this equation is a solvent in a dilute solution. An equilibrium constant, K eq, is a variable that describes a chemical reaction's tendency to proceed to completion, meaning all the reactants are converted to products. Definition of equilibrium constant in the AudioEnglish. In this experiment the reaction between ethyl acetate and methyl alcohol (or methyl acetate and ethyl alcohol) is monitored to its equilibrium state chromatographically. ] The equilibrium constant for a generic acid (HA) will further illustrate the difference between weak and strong acids. COCl2 (g) = CO (g) + Cl2 (g) My Answer: To find the reverse. In 1864, Peter Waage and Cato Maxmilian Guldberg (both of Norway) published the modern meaning of the equilibrium constant. The equilibrium constant for formation of a hydrate of acetone is 1. Here is the Equilibrium constant formula for calculating equilibrium constant Kp using partial pressures for the given chemical equation. At equilibrium, the expenditures of the forward and opposite reactions would be the comparable. Experiment 6: Determination of the Equilibrium Constant for Iron Thiocyanate Complex The data for this lab will be taken as a class to get one data set for the entire class. Knowledge of the equilibrium constant for the dominant isotopic species can then be used to calculate the individual isotope equilibrium constants. Equilibrium constant equation. Recall from Week 1 Notes that equilibrium reactions have forward and reverse reactions. Equilibrium chemistry is concerned with systems in chemical equilibrium. 314 J mol-1 K-1. 0 liter container. The Magnetic Resonance Research Center (MRRC) at ASU is the regional southwest resource for characterization and structure determination of proteins, DNA, biomolecules, chemical compounds and solid materials by nuclear magnetic resonance (NMR). ) To determine the equilibrium constant for the reaction of iron (III) and thiocyanate to form the thiocyanatoiron(III) complex ion using spectrophotometric data. How to calculate K, and how to use K to determine if a reaction strongly favors products or reactants at equilibrium. the equilibrium constant, also known as K eq, is defined by the following expression: where [A] is the molar concentration of species A at equilibrium, and so forth. The law of mass action is represented by the equilibrium expression: ' [ ] [ ] = = B. When something is in equilibrium, the vector sum of all forces acting on it = 0. 29 M What is the equilibrium constant of this reaction?. 1 and there have been about 6 versions of Windows since. 4 mole of iodine and 2. Reversible reactions, equilibrium, and the equilibrium constant K. 34 moles each of Brp (g) and C12 (g) are introduced in a container which has a volume Of 11. Equilibrium constant definition is - a number that expresses the relationship between the amounts of products and reactants present at equilibrium in a reversible chemical reaction at a given temperature. Though equilibrium can be attained from either side, the way equilibrium is represented is important for equilibrium constant calculation. The Equilibrium Constant Expression. 3) Carbonic acid equilibrium In an open system, the partial pressure of CO 2 (g) is relatively constant at P (CO 2 ) = 0. The equilibrium constant K is the value of Q when the reaction is at equilibrium. The extent of equilibrium. Determination of an Equilibrium Constant Introduction It is frequently assumed that reactions go to completion, that all of the reactants are converted into products. Calculate the equilibrium constant Kp for the reverse reaction at the same temperature. Free learning resources for students covering all major areas of biology. An exothermic reaction, with , tends to give , implying that the forward reaction is favored. When the equilibrium favors reactants Δ G > 0 and K eq < 1. Equilibrium Constant Bettina Mae De Mesa 3/20/2014 De Mesa 2 Abstract The main purpose of this lab was to determine the equilibrium constant within a chemical reaction with the utilization of a spectrophometer. Consider the following reaction 2 SO2 (g) + O2 (g) 2 SO3 (g) Write the equilibrium expression, Kc. 65 x 104 C mol-1. Thermal equilibrium is an important concept in thermodynamics. An equilibrium constant, designated by a upper case K, is the ratio of the equilibrium concentrations of reaction products to reactants or vice versa. The equilibrium constant for this equilibrium is K = p(O 2)/c(O 2). We are first dealing with shift in "equilibrium constant" then we will deal with effect on "equilibrium position". The equilibrium constant also provides useful thermodynamic information about the changes in free energy, enthalpy, and entropy in the course of a chemical reaction. The equilibrium constant is given by the equilibrium law equation Substitute in the units for each of the components in the equation: It shoiuld be pretty clear that the units on the top of the sum are equal to the units on the bottom and so they cancel out:. R = gas constant = 8. where K is a constant independent of initial composition, known as the equilibrium constant. The color in the test tube became a deeper red color because the equilibrium shifted to make more products. The fourth O2 equilibrium binding constant, K4, measured by kinetic techniques, could be used to ana- lyze equilibrium curves for either native or cross- linked hemoglobin. A large value for K c indicates that equilibrium is attained only after the reactants have been largely converted into products. What is 'Economic Equilibrium '. 2 Procedure. Concentration Changes in Equilibrium Reactions. Keywords: dimerization constant, heavy water. ) To determine the concentration of an unknown by evaluating the relationship. Find the equilibrium weight of CO2 if 2g of CaCo3, 2g of CaO, and 0. The reaction which does not undergo an equilibrium shift when only the volume is changed. For instance, much experimental work is performed under conditions of constant temperature. In addition, the equilibrium constant expression is nothing but the quotient of concentrations of products and concentrations of reactants. Solubility equilibrium is the equilibrium associated with dissolving solids in water to form aqueous solutions. Dissociation of PCl5 - Equilibrium constants in terms of degree of dissociation Phosphorus pentachloride dissociates in gas phase to give PCl3 and Cl2. From this the equilibrium expression for calculating K c or K p is derived. 0826813347e-010 This process is not favorable at 25°C. The resulting K can be used to predict other equilibrium positions. The chemical equilibrium constant is a numeric value that shows us the extent to which a particular reaction is carried out. In general, we use the symbol KKKK or KcK_\text{c}KcK, start subscript, c, end subscript to represent equilibrium constants. Equilibrium constant definition is - a number that expresses the relationship between the amounts of products and reactants present at equilibrium in a reversible chemical reaction at a given temperature. These basic principles can help you determine an unknown equilibrium constant by combining known constants. When chemists talk about equilibrium constants, they call reactions with large K values favorable and reactions with small K values unfavorable. Equilibrium of Constant-Temperature System A knowledge of the equilibrium conditions for an isolated system permits us to deduce similar conditions for other situations of physical interest. Enjoy the videos and music you love, upload original content, and share it all with friends, family, and the world on YouTube. 528 Initially, a gas containing 20% CH4 and 80% H20 is present at 2000k & P-latm. The equilibrium constant for the formation of iron(III) thiocyanate complex ion is to be determined. Since at equilibrium there is very little sucrose left, it is necessary to obtain the equilibrium constant for this process by appropriate combination of the equilibrium constants or Gibbs energy changes for the following processes. IB Chemistry standard level notes on the position of equilibrium. equilibrium "position" forward or backward (LeChâtelier's Principle). The value of the equilibrium constant for a given reaction at a specified temperature does not change if the concentration of a reactant or product changes. *NOTE: Change in concentration, pressure, catalyst, inert gas addition, etc. 3 Expressing Equilibria with Pressure Terms: Relation between K c and K p 17. How constant is its value? 4. Equilibrium Constant 3 7. Therefore the synthesis of oxyhemoglobin (foreword. equilibriums and the equilibrium constant would be rewritten as Kp to define that all values are units of pressure. After a thorough understanding of the two topics, the instructor will give a brief introduction to the ICE table. The net rate of formation of any species is equal to its rate of formation in the forward reaction plus its rate of formation in the reverse reaction: At equilibrium, rate net 0 and the rate law must reduce to an equation that is thermodynamically consistent with the equilibrium constant for the reaction. constants multiplied together for net reactions involving 2+ steps ; do not include pure solids, pure liquids, or solvents in finding constant ; For the reaction CaCo3(s) >> CaO(s) + CO2(g), K = 0. 15 K, pHs in the range 5-9, and ionic strengths in the range zero to about 0. We find the same results as those given by Henley and Seader in Equilibrium-Stage Separation Operations in Chemical Engineering, Wiley, 1981 (example 4-10 page 175). The above formulations (1. In this experiment we will study the equilibrium properties of the reaction between iron (III) ion, Fe3+,. Fine come on in of a great night. Students often get confused about how it is possible for the position of equilibrium to change as you change the conditions of a reaction, although the equilibrium constant may remain the same. A reaction that has a large equilibrium constant has _____? A) a faster reaction rate than a reaction with a small equilibrium constant. where K is a constant independent of initial composition, known as the equilibrium constant. 1 The continuous model. The Meaning of the Equilibrium Constant - Oneonta. Concept of force, units. Question: The decomposition of N 2 O 4(g) to produce NO 2(g) is an endothermic chemical reaction which can be represented by the following chemical equation: N 2 O 4(g) ⇋ 2NO 2(g) At 25°C the value of the equilibrium constant, K c is 4. 106 M [I 2 ] = 0. This section is fairly straightforward and just requires the student to appreciate the relationship between the actual values of the equilibrium constant Kc and the extent of the reaction. Solubility product equilibrium constant (K sp) - The product of the equilibrium concentrations of the ions in a saturated solution of a salt. 314472 J · K-1 T = temperature (Kelvin) F = Faraday's constant = 9. The equilibrium constant is defined by equation as −∆ = RT G K exp rxn (9) for the stoichiometry given by equation 1 the equilibrium constant is defined in terms of activities as EB styrene H a a a K = 2 (10). 1 x 1012 H2PO4- HPO42- + H+ 6. For example, [A] is the concentration of substance A. For our examples, assign x to the decrease in pressure of each reactant. Introduction. 314472 J · K-1 T = temperature (Kelvin) F = Faraday's constant = 9. These variables include the ones discussed in class such as pressure and temperature. Equilibrium - Theory In HYSYS, for most reactions you will need to input the equilibrium constant as a function of temperature. The ΔG (Gibbs free energy change) of a system at equilibrium is 0. The equilibrium constant for a particular reaction is specific for that reaction and changes only with variations in temperature. Recall from Week 1 Notes that equilibrium reactions have forward and reverse reactions. Equilibrium constants (Keq) are a way of the quotient of a reaction which has reached equilibrium. Lesson 8: Equilibrium Constants As its name suggests, "equilibrium" is a balance - a balance between the forward and reverse rates of a chemical reaction. The equilibrium constant for this reaction, called the water dissociation constant, K w, is 1. Despite the failure of this derivation, the equilibrium constant for a reaction is indeed a constant, independent of the activities of the various species involved, though it. the equilibrium constant, also known as K eq, is defined by the following expression: where [A] is the molar concentration of species A at equilibrium, and so forth. Experimental observations therefore reveal the criteria for maintaining a system in equilibrium (assuming the system has the potential to reach equilibrium as opposed to going to completion): constant temperature and a closed system. Equilibrium Constants 3-2 3. What is the equilibrium constant for the following reaction?. Problem: For the reaction H 2 (g) + I 2 (g) ↔ 2 HI(g) At equilibrium, the concentrations are found to be [H 2 ] = 0. Chemical Equilibrium Consider a reversible reaction taking place at constant temperature: aA + bB cC + dD The reactantsA and B combine to form productsC and D.

format: plain


text:
1
JEE Main 2022 (Online) 25th July Morning Shift
Numerical
+4
-1

If the maximum value of the term independent of $$t$$ in the expansion of $$\left(\mathrm{t}^{2} x^{\frac{1}{5}}+\frac{(1-x)^{\frac{1}{10}}}{\mathrm{t}}\right)^{15}, x \geqslant 0$$, is $$\mathrm{K}$$, then $$8 \mathrm{~K}$$ is equal to ____________.

2
JEE Main 2022 (Online) 29th June Evening Shift
Numerical
+4
-1

Let the coefficients of x$$-$$1 and x$$-$$3 in the expansion of $${\left( {2{x^{{1 \over 5}}} - {1 \over {{x^{{1 \over 5}}}}}} \right)^{15}},x > 0$$, be m and n respectively. If r is a positive integer such that $$m{n^2} = {}^{15}{C_r}\,.\,{2^r}$$, then the value of r is equal to __________.

3
JEE Main 2022 (Online) 28th June Morning Shift
Numerical
+4
-1

The number of positive integers k such that the constant term in the binomial expansion of $${\left( {2{x^3} + {3 \over {{x^k}}}} \right)^{12}}$$, x $$\ne$$ 0 is 28 . l, where l is an odd integer, is ______________.

4
JEE Main 2022 (Online) 27th June Evening Shift
Numerical
+4
-1

If the sum of the coefficients of all the positive powers of x, in the Binomial expansion of $${\left( {{x^n} + {2 \over {{x^5}}}} \right)^7}$$ is 939, then the sum of all the possible integral values of n is _________.

JEE Main Subjects
Physics
Mechanics
Electricity
Optics
Modern Physics
Chemistry
Physical Chemistry
Inorganic Chemistry
Organic Chemistry
Mathematics
Algebra
Trigonometry
Coordinate Geometry
Calculus
EXAM MAP
Joint Entrance Examination


text:
1. 12.Algorithmic thresholds for tensor PCA. With Gerard Ben Arous and Aukosh Jagannath. 2018.

2. 11.Bounding flows for spherical spin glass dynamics. With Gerard Ben Arous and Aukosh Jagannath. 2018.

3. 10.Random-cluster dynamics in Z^2: rapid mixing with general boundary conditions. With Antonio Blanca and Eric Vigoda Submitted. 2018.

4. 9.Zero-temperature dynamics in the dilute Curie-Weiss model. With Charles Newman and Daniel Stein. Journal of Statistical Physics. 2017.

5. 8.Concentration inequalities for polynomials of contracting Ising models. With Eyal Lubetzky and Yuval Peres. Electronic Communications in Probability 2017.

6. 7.Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. With Eyal Lubetzky and Yuval Peres. Extended abstract in SODA 2018. 2017.

7. 6.The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions. With Eyal Lubetzky. Electronic Journal of Probability. 2017.

8. 5.Ising model: local spin correlations and conformal invariance. With Clement Hongler and S. C. Park. Communications in Mathematical Physics, to appear. 2016.

9. 4.Quasi-polynomial mixing of critical 2D random cluster models. With Eyal Lubetzky. Submitted. 2016.

10. 3.On the spectral gap of spherical spin glass dynamics. With Aukosh Jagannath. Annales Institut Henri Poincare (B). 2016.

11. 2.Mixing times of critical 2D Potts models. With Eyal Lubetzky. Communications on Pure and Applied Mathematics. 2016.

12. 1.Asymptotics of height change on toroidal Temperleyan dimer models. With Julien Dubedat. Journal of Statistical Physics. 2015.

Preprints and publications


text:
Degrees of Freedom of Interference Channels with Hybrid Beam-forming

# Degrees of Freedom of Interference Channels with Hybrid Beam-forming

Sung Ho Chae,  and Cheol Jeong,  The authors are with the DMC R&D Center, Samsung Electronics, Suwon, Republic of Korea.
###### Abstract

We study the sum degrees of freedom (DoF) of interference channels with hybrid beam-forming in which each transmitter uses antennas and RF chains and each receiver uses antennas and RF chains, where and , , and hybrid beam-forming composed of analog and digital precodings is employed at each node. For the two-user case, we completely characterize the sum DoF for an arbitrary number of antennas and RF chains by developing an achievable scheme optimized for the hybrid beam-forming structure and deriving its matching upper bound. For a general -user case, we focus on a symmetric case where , , , and , , and obtain lower and upper bounds on the sum DoF, which are tight when is an integer. The results show that hybrid beam-forming can increase the sum DoF of interference channel under certain conditions while it cannot improve the sum DoFs of point-to-point channel, multiple access channel, and broadcast channel. The key insights on this gain is that hybrid beam-forming enables users to manage inter-user interference better, and thus each user can increase the dimension of interference-free signal space for its own desired signals.

Degrees of freedom, hybrid beam-forming, interference alignment, interference channel

## I Introduction

Mobile data traffic has been growing dramatically as the number of mobile smart devices is increasing rapidly in recent years [1]. To accommodate tremendous demand on mobile data traffic, the cell capacity can be largely increased by deploying a very large number of antennas at base stations (BSs), often referred to as a massive multiple-input multiple-output (MIMO) system [2, 3]. The massive MIMO system, however, has hardware constrains that come from using a few hundred antennas. For a conventional antenna array structure, each antenna needs to have a dedicated RF chain. This naturally leads to an increment in the circuit size, power consumption, and device cost proportionally to the number of antennas, and hence it can be a serious problem in a practical point of view especially for massive MIMO systems. Therefore, to resolve this problem, a hybrid beam-forming structure with a lower number of RF chains than the number of antenna elements has been recently introduced as a practical solution [4, 5].

As an alternative approach to increase the cell capacity, millimeter-wave (mmWave) communications have attracted great attention recently [6]. The mmWave band from 30 to 300 GHz provides abundant contiguous frequency resources while frequency bands under 5 GHz used for legacy cellular communications are very crowded and fragmented. The main advantage in mmWave communications is that a very high data rate can be supported using a very large bandwidth at mmWave bands. However, one of major drawbacks is the high induced path loss due to the propagation loss and absorption loss at mmWave bands [7]. Fortunately, this high path loss can be effectively compensated by a high beam-forming gain obtained from a large number of antenna elements that can be packed into a small form factor due to the small wavelength in mmWave bands. To support a single stream only, the analog beam-forming, which is simply implemented by controlling attenuators and phase shifters of the antenna array to steer a directional beam, is enough to be considered. However, to transmit multiple streams, the hybrid beam-forming structure, where analog beam-forming is performed at RF domain and antenna arrays are connected to a relatively small number of digital paths, should be considered to get the multiplexing gain [8, 9].

As mentioned above, the hybrid beam-forming architecture can play a key role in the next generation communications (e.g., massive MIMO and/or mmWave communications) and hence has been widely studied recently [8, 9, 10, 11, 12]. In [8], precoders and combiners are designed using a sparse reconstruction approach. In [10], baseband and RF beams are designed for multiuser downlink spatial division multiple access (SDMA). In addition, a hybrid precoding algorithm based on a hierarchical codebook is proposed in [11]. Furthermore, a hybrid precoder is proposed for massive multiuser MIMO systems in [12]. While there are some works on hybrid beam-forming structures, however, to the best of our knowledge, the degrees of freedom (DoF) gain from hybrid beam-forming has not been analyzed before.

### I-a Previous Works

The DoF, which is also known as a capacity pre-log, gives the capacity approximation at high signal to noise ratio (SNR) regime. For example, for the point-to-point (PTP) channel with transmit antennas and receive antennas, it is well known that the capacity increases with the growth rate at high SNR [13, 14]. Since exact capacity characterization is generally still unknown even for simple networks (e.g., two-user interference channel), instead of obtaining an exact capacity, approximate characterization by finding the optimal DoF has been studied in many networks recently [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31].

Specifically, for the two-user interference channel, the sum DoF has been completely characterized, where zero-forcing precoding has been shown to be enough to achieve the optimal DoF [15]. For a general -user interference channel, a novel interference management technique called interference alignment has been proposed in [16, 19], which achieves the optimal sum DoF of . Later this scheme has been extended to MIMO configurations both for rich scattering environment [23, 22] and poor scattering environment [29, 30, 31]. Furthermore, beyond the interference channels, the idea of interference alignment has been successfully adapted to various networks, e.g., see [17, 18, 19, 20, 21, 24, 25, 26, 27, 28] and references therein.

### I-B Contributions

In this paper, our primary goal is to answer if hybrid beam-forming can increase the sum DoF of interference channels. To this end, motivated by the aforementioned previous works, we propose zero forcing and interference alignment schemes optimized for the hybrid beam-forming structure. In addition, we also derive a new upper bound on the sum DoF when hybrid beam-forming is employed at each node. For the two-user case, this upper bound coincides with the achievable sum DoF of the proposed scheme, thereby completely characterizing the sum DoF. For a general -user case, our proposed scheme can achieve the upper bound when is an integer, where and denote the number of antennas at each transmitter and receiver, respectively. As a consequence of the result, we show that hybrid beam-forming can indeed improve the sum DoF of the -user interference channel under certain conditions. This is in contrast to the PTP channels, multiple access channel (MAC), and broadcast channel (BC) cases in which hybrid beam-forming cannot increase the sum DoF (see Section III). The key insight behind this gain is that hybrid beam-forming enables users to manage interference better, and thus each user can increase the dimension of interference-free signal space which can be used for its own desired signals.

### I-C Organization

The rest of this paper is organized as follows. In Section II, we describe the system model and sum DoF metric considered in this paper. In Section III, we give an intuition as to how hybrid beam-forming can increase the sum DoF through motivating examples. In Section IV, we present and discuss about the main results of this paper. In addition, we provide numerical results which show the performance improvement from hybrid beam-forming in Section V. In Sections VI and VII, we provide the proofs of the main theorems. Finally, we conclude the paper in Section VIII.

### I-D Notations

Throughout the paper, we will use , , and to denote a matrix, a vector, and a scalar, respectively. For a rational number , the notation denotes the integer part of . For matrix , let , , and denote the transpose, the complex conjugate transpose, and the norm of , respectively. In addition, let and denote the determinant and the rank of , respectively. The notations and denote the identity matrix and zero matrix, respectively. We write if .

## Ii System Model

Consider a -user interference channel with hybrid beam-forming, as shown in Fig. 1. Transmitter wishes to communicate with receiver only, while causing interference to all the other receivers. In addition, transmitter uses antennas and RF chains and receiver uses antennas and RF chains, where and , . Specially, when and , , we call the corresponding channel as a full digital channel.

### Ii-a Channel Model

Similar to previous works [8, 10], in this paper we assume that transmitter utilizes transmit hybrid beam-forming which consists of an analog precoder and an digital precoder as depicted in Fig. 1, where denotes the number of streams of user .111As compared to the hybrid beam-forming structure introduced in [8, 10], in this paper, coefficients in can have different norms by relaxing the constraint that all entries are of equal norm. In practical point of view, this is feasible since we can implement by using both attenuators and analog phase shifters rather than using analog phase shifters only. In addition, based on this hybrid beam-forming, the input signal of transmitter at time slot , , is assumed to be given by

 xi(t) =V′i(t)x[b]i(t) =V′i(t)Vi(t)si(t),

where is the baseband-domain input vector and

 si(t)=[si,1(t)⋯si,di(t)]T

is the symbol vector of transmitter . Here, denotes the th symbol of user at time slot . Then the input and output relationship at RF domain is given by

 yj(t) =K∑i=1Hji(t)xi(t)+zj(t) =K∑i=1Hji(t)V′i(t)x[b]i(t)+zj(t) =K∑i=1Hji(t)V′i(t)Vi(t)si(t)+zj(t),

where is the channel matrix from transmitter to receiver , is the RF-domain received signal vector at receiver , and is the Gaussian noise vector at receiver whose entries are drawn from . We assume that all channel coefficients are independent and identically distributed (i.i.d) from a continuous distribution and known to all nodes.

After receiving , receiver applies receive hybrid beam-forming which consists of an analog precoder and a digital precoder as shown in Fig. 1. Specifically, by applying the analog precoder to the received signal at RF domain, we can obtain the input and output relationship at baseband domain as

 y[b]j(t)=K∑i=1H[b]ji(t)x[b]i(t)+z[b]j(t),

where , , and . If we further apply the digital precoder to the received signal at baseband domain, we finally get

 y[e]j(t)=K∑i=1H[e]ji(t)si(t)+z[e]j(t),

where , , and . Note that is the effective channel matrix which can be obtained after applying transmit hybrid beam-forming of transmitter and receive hybrid beam-forming of receiver .

Finally, by applying the aforementioned hybrid beam-forming strategy and assuming Gaussian signaling , the following average sum rate is achievable for a given transmit power  [32]:

 Rsum(P)≤E⎡⎢ ⎢⎣K∑i=1log∣∣Ai(t)+Pdi∑Kj=1H[e]ij(t)H[e]ij(t)∗∣∣∣∣Ai(t)+Pdi∑Kk=1,i≠kH[e]ik(t)H[e]ik(t)∗∣∣⎤⎥ ⎥⎦, (1)

where . Specifically, when all the interferences are eliminated via hybrid beam-forming, i.e., , and , (1) becomes

 Rsum(P) ≤E⎡⎢ ⎢⎣K∑i=1log∣∣Ai(t)+Pdi∑Kj=1H[e]ij(t)H[e]ij(t)∗∣∣|Ai(t)|⎤⎥ ⎥⎦ (2) =K∑i=1dilog(P)+o(log(P)). (3)

### Ii-B Encoding, Decoding, and Sum DoF

There are independent messages . For each transmitter , a message is mapped to an length codeword . To send the message , at time , transmitter sends . Here, we assume that each transmitter should satisfy the average power constraint , i.e., for . Then receiver decodes its desired message , based on its received signal.

A rate tuple is said to be achievable for the channel if there exists a sequence of codes such that the average probability of decoding error tends to zero as the code length goes to infinity. The capacity region of this channel is the closure of the set of achievable rate tuples . The sum DoF , which is also known as a sum-capacity pre-log, provides the sum capacity approximation at high SNR as222In this paper, when we derive lower and upper bounds on the sum DoF, we restrict our attention on the cases in which the hybrid beam-forming structure introduced in Section II-A is used.

 Csum(P)=max(R1,R2,…,RK)∈CK∑i=1Ri(P)=Γlog(P)+o(log(P)).

Equivalently, the sum DoF can be defined as .

## Iii Preliminary Discussion

To gain insights into the DoF gain from hybrid beam-forming, we begin with examining PTP channel, MAC, and BC cases. Note that the PTP channel, the -user MAC, and the -user BC can be obtained from the -user interference channel by allowing full cooperation among all the transmitters and among all the receivers, full cooperation among all the receivers only, and full cooperation among all the transmitters only, respectively. Here, we assume that hybrid beam-forming strategy (including digital precoder and analog precoder) for each channel is employed in a similar manner as in Section II.

### Iii-a Point-to-Point (PTP) Channel

Consider the PTP channel in which the transmitter uses RF chains and antennas and the receiver uses RF chains and antennas. The DoF of this channel is stated in the following lemma.

###### Lemma 1

For the PTP channel with hybrid beam-forming, the DoF is given by .

{proof}

We first provide a converse proof. Following a similar way described in Section II, we can write the input and output relationship of the PTP channel at time slot as

 y(t) =H(t)x(t)+z(t) =H(t)V′(t)x[b](t)+z(t),

where is the RF-domain output vector at the receiver, is the channel matrix from the transmitter to the receiver, and are the RF-domain input vector and the baseband-domain input vector at the transmitter, respectively, is the analog precoder of the transmitter, and is the Gaussian noise vector.

Now focus on the input and output relationship at baseband domain. By applying receive analog precoding at the receiver, we can get

 U′∗(t)y(t)=y[b](t)=H[b](t)x[b](t)+z[b](t),

where is the analog precoder of the receiver, , and . Since , we see that .

For achievability, we only use transmit antennas out of antennas of the transmitter and receive antennas out of antennas of the receiver to equivalently create a conventional full digital PTP channel with transmit antennas and receive antennas. Therefore, is achievable [13, 14], which completes the proof.

It is well known that the DoF of the full digital PTP channel with transmit antennas and receive antennas is equal to  [13, 14]. Therefore, from the result of Lemma 1, we see that adding more antennas only cannot increase the DoF of a PTP channel without increasing the number of RF chains, regardless of the values of and .

### Iii-B Multiple Access Channel (MAC) and Broadcast Channel (BC)

Now we consider the -user MAC and BC with hybrid beam-forming. For the MAC case, each transmitter uses RF chains and antennas and the receiver uses RF chains and antennas. For the BC case, the transmitter uses RF chains and antennas and each receiver uses RF chains and antennas. The DoFs of these channels are stated in the following lemmas.

###### Lemma 2

For the -user multiple access channel (MAC) with hybrid beam-forming, the DoF is given by .

{proof}

For a converse proof, we allow full cooperation among all the transmitters to form PTP channel. Then, from the result of Lemma 1, the sum DoF of this network is equal to . Since allowing cooperation does not reduce the capacity region [17], this is an upper bound of the original network, and thus

 ΓMAC≤min{K∑i=1Mi,N}.

For achievability, we use only antennas out of antennas of transmitter , , and antennas out of antennas of the receiver to form a conventional full digital MAC in a similar manner as in Lemma 1. Then, is achievable [15], which completes the proof.

###### Lemma 3

For the -user broadcast channel (BC) with hybrid beam-forming, the DoF is given by .

{proof}

We can easily prove Lemma 3 by following similar proof steps in Lemma 2 except the fact that we now allow full cooperation among all the receivers instead of transmitters for a converse proof. For brevity, we omit the rest of the proof steps.

From the results of Lemmas 2 and 3, adding more antennas only without more RF chains cannot increase the sum DoFs of MAC and BC, as in the PTP case. Therefore, we can see that when full cooperation is already allowed at either transmitter side or receiver side of the -user interference channel, hybrid beam-forming cannot further improve the DoF. However, as we will show in the following example, for the case in which full cooperation is not allowed so that there exist inter-user interferences, the sum DoF of an interference channel can be improved via hybrid beam-forming for certain cases.

### Iii-C Interference Channel: Motivating Example

Now we provide a simple example where hybrid beam-forming indeed improves the sum DoF. In the following example, we omit the time index for brevity.

###### Example 1

Consider the two-user interference channel where and , . We first set the analog precoder to satisfy for and . Since is the matrix and all channel coefficients are generic, we can easily find that satisfies these conditions. In addition, for the digital precoder of transmitter , we set , . Then, the received signal at each receiver is given by

 yi =HiiV′iVisi+HijV′jVjsj+zi =HiiV′isi+zi,

where is the transmitted symbol vector of user and . Since , we can achieve for each user, thus achieving . Note that for the two-user full digital interference channel, which has the same number of RF chains as in the two-user interference channel, only the sum DoF of two can be achieved. This shows that for some cases, the sum DoF of an interference channel can actually be increased by adding more antennas only without increasing the number of RF chains.

###### Remark 1

As shown in Example 1, by using more antennas, we can have a better ability to null out interferences from/to other users at RF domain. This enables users to secure more interference-free dimensions, and as a result, a higher sum DoF is achievable without any additional RF chains for some cases. However, despite this improved capability dealing with interferences, hybrid beam-forming does not always increase the DoF of an interference channel. For instance, as will be demonstrated in the next example, if all the interferences can be eliminated without the need to add more antennas, hybrid beam-forming cannot increase the sum DoF.

###### Example 2

Consider the two-user interference channel where , , , and , . By allowing full cooperation among transmitters and among receivers, we can get the PTP channel. Since the DoF of this channel is given by two from Lemma 1 and allowing full cooperation does not reduce the capacity region, the sum DoF of the two-user interference channel cannot be more than two. Note that the two-user full digital interference channel can also achieve the sum DoF of two [15]. Therefore, unlike in Example 1, adding antennas only cannot increase the sum DoF in this case. In fact, in this case, to achieve a higher DoF, we need to use more RF chains as well as more antennas. For example, if we use additional one RF chain and two RF chains at each transmitter and receiver, respectively, the channel becomes the two-user full digital interference channel, and we can now achieve the improved DoF of 4.

## Iv Main Results

In this section, we state and discuss about the main results of this paper. For the two-user case, the sum DoF is completely characterized for any antenna configuration. When , we focus on a symmetric case where , , , and , , and derive lower and upper bounds on the sum DoF. It is shown that two bounds are matched under a certain condition.

### Iv-a Two-user Case

For the two-user interference channel, we completely characterize the sum DoF as stated in the following theorem.

###### Theorem 1 (Two-user case)

For the two-user interference channel with hybrid beam-forming, the sum DoF is given by

 Γ=min{M1+M2,N1+N2,M1+N2,M2+N1,max{M′1,N′2},max{M′2,N′1}}

where and for .

{proof}

See Section VI for the proof.

###### Remark 2

For the case where and , , the sum DoF becomes

 Γ=min{M1+M2,N1+N2,max{M1,N2},max{M2,N1}},

which recovers the result for the two-user full digital interference channel in [15].

###### Remark 3

Note that when the condition

 min{max{M′1,N′2},max{M′2,N′1}}≥min{M1+M2,N1+N2,M1+N2,M2+N1}

is satisfied, the sum DoF becomes

 Γ =min{M1+M2,N1+N2,N1+M2,M2+N1} =min{M1,N1}+min{M2,N2},

which is the sum DoF of the interference-free channel. Therefore, we can see that by adding enough number of antennas at each node, all the users can utilize their full DoFs as if there is no interference.

DoF gain due to hybrid beam-forming: Consider a symmetric case where and . We plot the sum DoF as a function of with fixed in Fig. 2. For comparison, we also plot the sum DoF of the full digital case where the number of RF chains is the same as the hybrid beam-forming case. As can be seen in Fig. 2, although we add antennas only, we can achieve a higher DoF and it reaches up to the maximum value of , the sum DoF of the interference-free channel, when . The gain comes from the fact that hybrid beam-forming can null out more interferences without increasing the number of RF chains, as well as enhancing the capacity of PTP channel as reported in [8, 10].

### Iv-B K-user Case

When , we focus on a symmetric case where , , , and , . Under this configuration, we obtain lower and upper bounds on the sum DoF as stated in the following theorem, which are tight when is an integer.

###### Theorem 2 (K-user case)

For the symmetric -user interference channel with hybrid beam-forming, the following sum DoF is achievable:

 Γ≥⎧⎨⎩Kmin{M,N}if K≤R,Kmin{M,N,RR+1min{M′,N′}}if % K>R,

where . For converse, the sum DoF is upper bounded by

 Γ≤⎧⎪⎨⎪⎩Kmin{M,N}if K≤R,Kmin{M,N,max{M′,N′}R+1}if K>R.
{proof}

See Section VII for the proof.

###### Remark 4

Similar to the two-user case explained in Remark 2, for the case where and , Theorem 2 recovers the result for the -user full digital interference channel in [23].

###### Remark 5

It is easy to see that is a non-decreasing function of and . Intuitively, this is clear since having more antennas does not reduce the capacity region. Moreover, when each user can achieve the maximum DoF of as if there is no interference.

###### Corollary 1

By employing hybrid beam-forming, we can get at most two-fold DoF gain as compared to the full digital case in which the number of RF chains is the same as the hybrid beam-forming case. {proof} Let and denote the sum DoFs with hybrid beam-forming and full digital structures, respectively. For the two-user case, we have

 ΓhΓf =min{M1+M2,N1+N2,M1+N2,M2+N1,max{M′1,N′2},max{M′2,N′1}}min{M1+M2,N1+N2,max{M1,N2},max{M2,N1}} ≤min{M1,N1}+min{M2,N2}min{M1+M2,N1+N2,max{M1,N2},max{M2,N1}} ≤min{M1,N1}+min{M2,N2}max{min{M1,N1},min{M2,N2}} ≤2max{min{M1,N1},min{M2,N2}}max{min{M1,N1},min{M2,N2}} =2

In addition, for the general -user case, we have

 ΓhΓf ≤Kmin{M,N}KLL+1min{M,N} =L+1L ≤2,

where . This completes the proof.

DoF gain due to hybrid beam-forming: Consider the three-user case where . First, we set and plot the sum DoF as a function of with fixed and in Fig. 3. In addition, we consider another scenario in which additional antennas are employed only at transmitters, i.e., , and again plot the sum DoF as a function of . As can be seen in the figure, by using hybrid beam-forming, we can achieve a higher DoF and interestingly, it can reach up to the maximum DoF of six even when hybrid beam-forming is applied at transmitters only. Furthermore, note that when achieving this DoF, interference alignment combined with hybrid beam-forming is employed. From this point, we can see that hybrid beam-forming can provide an improved capability not only nulling out interferences but also aligning interferences at RF domain.

Now, we examine a tendency of the sum DoF with respect to with the fixed number of antennas and RF chains at each node. Specifically, we set and plot the sum DoFs when and in Fig. 4. For comparison, we also plot the sum DoF of the full digital case where the number of RF chains is the same as the hybrid beam-forming case. From Fig. 4, we see that hybrid beam-forming can improve the sum DoF for all values of , and moreover, the slope also increases as the number of additional antennas at each receiver increases.

## V Numerical Simulation

In this section, we numerically evaluate the average sum rate performance of the proposed hybrid beam-forming schemes for and cases to show that the sum DoFs stated in Theorems 1 and 2 are indeed achievable. For comparison, the sum DoFs of the full digital and the interference-free cases are also plotted. Here, we assume Rayleigh fading environment where each channel coefficient is drawn i.i.d from . In addition, we assume that all the noise power is normalized to unity and thus . Furthermore, to clearly capture the sum DoFs from the sum-rate graphs, we plot the average sum rates as a function of .

### V-a Average Sum Rate for the Two-user Case

In Fig. 5, the average sum rates are plotted as a function of , where and . Note that the sum DoFs can be observed from the slopes in the figure. We can see that the sum DoFs obtained by the simulation are well matched with the sum DoFs stated in Lemma 1 and Theorem 1. Here, when the simulation is performed, the number of streams of hybrid beam-forming for each user is set by and for and for by following Theorem 1.

As shown in the figure, the full digital scheme can only achieve the sum DoF of two, while the sum DoF of the interference-free channel is four. When hybrid beam-forming is employed, we can see by simulation that the sum DoF can be improved and even reach up to the interference-free DoF, as shown in Theorem 1, and therefore the performance gap between hybrid beam-forming and full digital cases dramatically increases as the SNR increases.

### V-B Average Sum Rate for the Three-user Case

As in the previous subsection, the average sum rate is plotted as a function of in Fig. 6, where . When hybrid beam-forming is used, we consider the two different scenarios in which additional antennas are employed only at transmitters, i.e., for and 6, and additional antennas are employed both at transmitters and receivers, i.e., for and 6. Here, we adopt the distributed interference alignment333Note that the achievable scheme proposed in Theorem 2 requires an arbitrary large number of symbol extension. Therefore, in this subsection, instead of adopting the achievable scheme in Theorem 2 directly, we employ the DIA algorithm to numerically show that the sum DoF stated in Theorem 2 is indeed feasible. Here, Theorem 2 provides theoretical guidance when selecting a suitable number of streams for each user. (DIA) algorithm proposed in [33] for numerical simulation and the number of streams of hybrid beam-forming used for the simulation is given by Theorem 2. The slopes in the figure show that the sum DoFs stated in Theorem 2 is indeed achievable.

The full digital scheme can only achieve the sum DoF of three, while the sum DoF of the interference-free channel is six as shown in the figure. As in the two-user case, the sum DoF of the full digital scheme is only half of that of the interference-free channel. When and , the hybrid beam-forming can achieve the maximum sum DoF of six as if there is no interference between users. Interestingly, for the case in which additional antennas are employed only at transmitters , the sum DoF can also be increased as compared to the full digital case, and the performance gain over the full digital case increases as the number of additional antennas increases.

## Vi Proof of Theorem 1

### Vi-a Achievability

In our achievable scheme, we will use only transmit RF chains out of RF chains of transmitter and receive RF chains out of RF chains of receiver , for all . Hence, from now on, we can equivalently consider the interference channel instead of the original channel, the interference channel. In addition, since our achievable scheme operates in a single time slot, we omit the time index for brevity.

We design the input signal of transmitter as

 xi=V′iVisi,

where is the transmit analog precoder, is the transmit digital precoder, and is the vector of transmitted Gaussian symbols of user . To be specific, beam-forming vectors in can be decomposed into two parts:

 V′i=[V′iiV′i0]
• denotes the th beam-forming vector in such that and , where . Note that since the size of is given by and channel matrices are drawn i.i.d from a continuous distribution, the maximum number of linearly independent beam-forming vectors satisfying this condition is . Let denote the number of such vectors.

• denotes the th beam-forming vector in whose coefficients are randomly generated from a continuous distribution and , where has a finite value. Hence, and for with probability one. Let denote the number of such vectors. In addition, we further restrict and to satisfy .

In summary, we choose , , , , , and to satisfy the following conditions.

 0≤d1=d11+d10≤min(M1,N1) (4) 0≤d2=d22+d20≤min(M2,N2) (5) 0≤d11≤max(0,M′1−N′2) (6) 0≤d22≤max(0,M′2−N′1) (7) 0≤d1+d20≤N′1 (8) 0≤d2+d10≤N′2 (9)

Then the received signal at receiver at RF domain is given by

 yi =Hiixi+Hijxj+zi =HiiV′iVisi+HijV′jVjsj+zi =HiiV′iVisi+Hij[0M′j×djjV′j0]Vjsj+zi, (10)

where (10) is due to the properties of and .

Now we explain the beam-forming matrix at receiver . Denote as the receive analog precoder and as the receive digital precoder. We set such that and . Since we have

 rank(HiiV′iVi)=di rank(Hij[0M′j×djjV′j0]Vj)=dj0 di+dj0≤N′i,

we can find satisfying these conditions. Therefore, after applying receive analog precoding, we obtain

 U′∗iyi =U′∗iHiiV′iVisi+U′∗iHij[0M′j×djjV′j0]Vjsj+U′∗izi =U′∗iHiiV′iVisi+U′∗izi.

Recall that . Now, we set and as the left and right singular matrices of the matrix , respectively. Then we get parallel AWGN channels for user after applying the receive digital precoding as follows:

 U∗iU′∗iyi=y[e]i =U∗iU′∗iHiiV′iVisi+U∗iU′∗izi =Λisi+z[e]i,

where is the diagonal matrix with the singular values of on the diagonal and . Therefore, we can see that each user achieves DoF via the proposed scheme, and thus the achievable total DoF is given by .

Finally, by evaluating the conditions (4)–(9) using the Fourier-Motzkin elimination, we get the desired bound:

 Γ≥min{M1+M2,N1+N2,M1+N2,M2+N1,max{M′1</


text:
Search:

# Geometry Optimization

A geometry optimization is automatically carried out, as soon as {$*$}s are specified in the Z-Matrix after the variable names.

The default choice is a search for a minimum on the potential energy surface using analytically evaluated gradients within a Quasi-Newton scheme. The Hessian update is then done using the BFGS scheme starting with a unit matrix in the first iteration.

If a Hessian matrix is available, a Newton-Raphson scheme is applied.

A Powell-update of the Hessian (instead of the BGFS update) is performed when GEO_METHOD=RFA is specified. A transition-state search is requested via GEO_METHOD=TS (for a detailed description how transition states can be determined, see the corresponding example and recommendations)

The convergence criterium for completion is set via GEO_CONV=N. The value is specified in Hartree/bohr and the default is N=5 leading to a threshold value of 10**-5.

The maximum number of iterations is specified via GEO_MAXCYC. Default is here 50.

It is in many cases advantageous to perform the geometry optimization using a pre-calculated force-constant matrix. Such a force-constant matrix can be supplied by simply copying the corresponding FCM or FCMINT file into the working directory. Another option is to compute the force-constant matrix within the same job at the same or at a lower level than the actual geometry optimization. This can be accomplished by specifying a %fcm section in the ZMAT file which contains all the relevant information for this preceeding force-constant calculation.

Examples


text:
# Approximating a projection by a sum of elementary tensors with a certain property

Let $$A$$ and $$B$$ be two C$$^{*}$$-algebras and suppose we have a non-zero projection $$p\in A\otimes B$$. (We can assume $$A$$ is nuclear, so that there is only one possible tensor product.)

Does there exist a choice of elements $$a_{1},\ldots,a_{n}\in A$$ and $$b_{1},\ldots,b_{n}\in B$$ such that:

1. $$\left\|\left(\sum_{i=1}^{n}a_{i}\otimes b_{i}\right)-p\right\|<\frac{1}{2}$$;
2. If $$\pi$$ is a non-zero irreducible representation of $$A$$ and $$(\pi\otimes\operatorname{id})(p)=0$$, then $$\pi\left(\sum_{i=1}^{n}|a_{i}|\right)=0$$?

All I can deduce is that for a given choice of $$a_{i}$$'s and $$b_{i}$$'s, and and irreducible representation $$\pi$$ of $$A$$, we have $$\left\|\sum_{i=1}^{n}\pi(a_{i})\otimes b_{i}\right\|=\left\|(\pi\otimes \operatorname{id})\left(\left(\sum_{i=1}^{n}a_{i}\otimes b_{i}\right)-p\right)\right\|\leq \left\|\left(\sum_{i=1}^{n}a_{i}\otimes b_{i}\right)-p\right\|<\frac{1}{2},$$ provided that $$(\pi\otimes\operatorname{id})(p)=0$$.

• Are you sure you've stated the problem correctly? What you have written is clearly false, because you can always throw $x\otimes y - x\otimes y$ into the sum. So you would have to have $\pi(|x|) = 0$ for all $x$. – Nik Weaver Apr 13 '20 at 16:23
• I am not picky about what the $a_{i}$'s and $b_{i}$'s are so long that the approximation for $p$ holds. I guess I am wondering if there is a way to choose them so that the quoted result is always true. – ervx Apr 13 '20 at 16:59
• Given your "I guess I am wondering" could you please edit your question to give a more precise statement of what hypotheses you are assuming and what conclusion you want? – Yemon Choi Apr 13 '20 at 17:34
• I have updated the question. – ervx Apr 13 '20 at 17:42
• Could you change to a more specific title? – YCor Apr 13 '20 at 17:48

Yes, this is possible, assuming that $$A$$ (or $$B$$) is nuclear. The same argument below (using that exact $$C^\ast$$-algebras are locally reflexive) also works if $$A$$ or $$B$$ is exact and the tensor product is the spatial (aka minimal) tensor product.
The role of nuclearity is that any two-sided closed ideal $$J \subseteq A\otimes B$$ is the closed linear span of all tensor products $$I_A \otimes I_B$$ of two-sided closed contained in $$J$$, see Corollary 9.4.6 in Brown and Ozawa's book. Now, let $$J_A \subseteq A$$ be the intersection of all two-sided, closed ideals $$J \subseteq A$$ such that $$p \in J \otimes B$$ and let $$I:= \bigcap J \otimes B$$ where the intersection is indexed by such $$J$$. Clearly $$J_A \otimes B \subseteq I$$. For the converse (which is not as trivial as it a priori looks), take $$I_A \otimes I_B \subseteq I$$ where $$I_A$$ and $$I_B$$ are two-sided closed ideals in $$A$$ and $$B$$ respectively. Then $$I_A \subseteq J_A$$ and $$I_B \subseteq B$$, so $$I_A \otimes I_B \subseteq J_A \otimes B$$. By nuclearity of $$A$$, $$I$$ is the closed linear span of all such $$I_A\otimes I_B$$, so $$I = J_A \otimes B$$. In particular, $$p\in J_A \otimes B$$.
Now, let $$a_1,\dots, a_n \in J_A$$ and $$b_1,\dots, b_n \in B$$ such that $$$$\| \sum_{i=1}^n a_i \otimes b_i - p \| < 1/2.$$$$ Let $$\pi \colon A \to \mathcal B(\mathcal H)$$ be an irreducible representation such that $$(\pi \otimes \mathrm{id}_B)(p) = 0$$. The image of $$(\pi \otimes \mathrm{id}_B)$$ is canonically $$\pi(A) \otimes B$$, so by nuclearity of $$A$$ (or $$B$$) and exactness of maximal tensor products, it follows that $$$$0 \to (\ker \pi)\otimes B \to A \otimes B \to \pi(A) \otimes B \to 0$$$$ is exact, so the kernel of $$(\pi \otimes \mathrm{id}_B)$$ is $$(\ker \pi )\otimes B$$. Hence $$p \in (\ker \pi)\otimes B$$ so $$a_1,\dots, a_n \in J_A \subseteq \ker \pi$$ by construction of $$J_A$$.
If $$A$$ or $$B$$ is exact, we get $$\ker (\pi \otimes \mathrm{id}_B)$$ either by using that $$A$$ is locally reflexive or $$B$$ is exact to get that $$$$0 \to (\ker \pi) \otimes_{\min{}} B \to A \otimes_{\min{}} B \to \pi(A) \otimes_{\min{}} B \to 0$$$$ is exact.


text:
##### LANGUAGES
modified on 14 September 2010 at 10:25 ••• 463,071 views

# Benchmarks performed with NWChem

This page contains a suite of benchmarks performed with NWChem. The benchmarks include a variety of computational chemistry methods on a variety of high performance computing platforms. The list of benchmarks available will evolve continuously as new data becomes available. If you have benchmark information you would like to add for your computing system, please contact one of the developers.

# Hybrid density functional calculation on the C240 Buckyball

Performance of the Gaussian DFT module in NWChem. This calculation involved performing a PBE0 calculation (in direct mode) on the on C240 system with the 6-31G* basis set (3600 basis functions). These calculations were performed on the Chinook supercomputer located at PNNL. Timings are per step for the various components. The input file is available.

# Parallel performance of Ab initio Molecular Dynamics using plane waves

AIMD Parallel timings for UO$_2^{2+}$+122H2O. These calculations were performed on the Franklin Cray-XT4 computer system at NERSC.
Exact exchange timings – 80 atom cell of hematite (cutoff energy=100Ry). These calculations were performed on the Franklin Cray-XT4 computer system at NERSC.
AIMD and AIMD/MM Parallel Timings for Zn2 + +64H2O (unit cell parameters SC=12.4 Angs. and cutoff energy =100Ry). These calculations were performed on the Chinook HP computer system at MSCF EMSL, PNNL.

# Parallel performance of the CR-EOMCCSD(T) method (triples part)

An example of the scalability of the triples part of the CR-EOMCCSD(T) approach for Green Fluorescent Protein Chromophore (GFPC) described by cc-pVTZ basis set (648 basis functions) as obtained from NWChem. Timings were determined from calculations on the Franklin Cray-XT4 computer system at NERSC. See the input file for details.

# Timings of CCSD/EOMCCSD for the oligoporphyrin dimer

CCSD/EOMCCSD timings for oligoporphyrin dimer (942 basis functions, 270 correlated electrons, D2h symmetry, excited-state calculations were performed for state of b1g symmetry, in all test calculation convergence threshold was relaxed, 1024 cores were used). See the [Media:input_p2ta.nw input file] for details.

```--------------------------------------------------------
Iter          Residuum       Correlation     Cpu    Wall
--------------------------------------------------------
1   0.7187071521175  -7.9406033677717   640.9   807.7
......
MICROCYCLE DIIS UPDATE: 10 5
11   0.0009737920958  -7.9953441809574   691.1   822.2
--------------------------------------------------------
Iterations converged
CCSD correlation energy / hartree =        -7.995344180957357
CCSD total energy / hartree       =     -2418.570838364838890

EOM-CCSD right-hand side iterations
--------------------------------------------------------------
Residuum       Omega / hartree  Omega / eV    Cpu    Wall
--------------------------------------------------------------

Iteration   1 using    5 trial vectors
0.7254630898708   0.2656229931076    7.22797  4471.5  5151.3

Iteration   2 using    6 trial vectors
0.1584284659595   0.0882389635508    2.40111   865.3  1041.2
```

# Current developments for high accuracy: GPGPU and alternative task schedulers

Currently various development efforts are underway for high accuracy methods that will be available in future releases of NWChem. The examples below shows the first results of the performance of the triples part of Reg-CCSD(T) on GPGPUs (left two examples) and of using alternative task schedules for the iterative CCSD and EOMCCSD.


text:
Blog > “Obvious” Does Not Imply “True”: The Minimal Superpermutation Conjecture is False

## “Obvious” Does Not Imply “True”: The Minimal Superpermutation Conjecture is False

August 22nd, 2014

One of my favourite examples of an “obvious” mathematical statement that is actually false is the “fact” that if $R,S,T \subseteq \mathbb{R}^n$ are vector spaces then

$\dim(R + S + T) = \dim(R) + \dim(S) + \dim(T) \\ {}_{{}_{{}_{.}}}\quad\quad\quad\quad\quad\quad\quad\quad - \dim(R\cap S) -\dim(R\cap T) -\dim(S\cap T) \\ {}_{{}_{{}_{.}}}\quad\quad\quad\quad\quad\quad\quad\quad+\dim(R\cap S\cap T).$

The reason that the above statement seems so obvious is that the similar fact $\dim(R + S) = \dim(R) + \dim(S) - \dim(R\cap S)$ does hold, so it’s very tempting to think  “inclusion-exclusion, yadda yadda, it’s simple enough to prove that it’s not worth writing down or working through the details”. However, it’s not true: a counterexample is provided by 3 distinct lines through the origin in $\mathbb{R}^2$.

There is another problem that I’ve been thinking about for quite some time that is also “obvious”: the minimal superpermutation conjecture. This conjecture was so obvious, in fact, that it appeared as a question in a national programming contest in 1998. Well, last night Robin Houston posted a note on the arXiv showing that, despite being obvious, the conjecture is false [1].

### Superpermutations

What is the shortest string that contains each permutation of “123” as a contiguous substring? It is straightforward to check that “123121321” contains each of “123”, “132”, “213”, “231”, “312”, and “321” as substrings (i.e., it is a superpermutation of 3 symbols), and it’s not difficult to argue (or use a computer search to show) that it is the shortest string with this property.

Well, we can repeat this question for any number of symbols. I won’t repeat all of the details (because I already wrote about the problem here), but there is a natural recursive construction that takes an (n-1)-symbol superpermutation of length L and spits out an n-symbol superpermutation of length L+n!. This immediately gives us an n-symbol superpermutation of length 1! + 2! + 3! + … + n! for all n. Importantly, it seemed like this construction was the best we could do: computer search verifies that these superpermutations are the smallest possible, and are even unique, for n ≤ 4.

Furthermore, it is not difficult to come up with some lower bounds on the length of superpermutations that seem to suggest that we have found the right answer. A trivial argument shows that an n-symbol superpermutation must have length at least (n-1) + n!, since we need n characters for the first permutation, and 1 additional character for each of the remaining n!-1  permutations. This argument can be refined to show that a superpermutation must actually have length at least (n-2) + (n-1)! + n!, since there is no way to pack the permutations tightly enough so that each one only uses 1 additional character (spend a few minutes trying to construct superpermutations by hand and you’ll see this for yourself). In fact, we can even refine this argument further (see a not-so-pretty proof sketch here) to show that n-symbol superpermutations must have length at least (n-3) + (n-2)! + (n-1)! + n!.

A-ha! A pattern has emerged – surely we can just keep refining this argument over and over again to eventually get a lower bound of 1! + 2! + 3! + … + n!, which shows that the superpermutations we already have are indeed minimal, right? Some variant of this line of thought seemed to be where almost everyone’s mind went when introduced to this problem, and it seemed fairly convincing: this argument is more or less contained within the answers when this question was posted on MathExchange and on StackOverflow (although the authors are usually careful to state that their method only appears to be optimal), and this problem was presented as a programming question in the 1998 Turkish Informatics Olympiad (see the resulting thread here). Furthermore, even on pages where this was acknowledged to be a difficult open problem, it was sometimes claimed that it had been proved for n ≤ 11 (example).

For the above reasons, it was a long time before I was even convinced that this problem was indeed unsolved – it seemed like people had solved this problem but just found it not worth the effort of writing up a full proof, or that people had found a simple way to tackle the problem for moderately large values of n like 10 or 11 that I couldn’t even dream of handling.

### The Conjecture is False

It turns out that the minimal superpermutation conjecture is false for all n ≥ 6. That is, there exists a superpermutation of length strictly less than 1! + 2! + 3! + … + n! in all of these cases [1]. In particular, Robin Houston found the following 6-symbol superpermutation of length 872, which is smaller than the conjectured minimum length of 1! + 2! + … + 6! = 873:

12345612345162345126345123645132645136245136425136452136451234651234156234152634
15236415234615234165234125634125364125346125341625341265341235641235461235416235
41263541236541326543126453162435162431562431652431625431624531642531462531426531
42563142536142531645231465231456231452631452361452316453216453126435126431526431
25643215642315462315426315423615423165423156421356421536241536214536215436215346
21354621345621346521346251346215364215634216534216354216345216342516342156432516
43256143256413256431265432165432615342613542613452613425613426513426153246513246
53124635124631524631254632154632514632541632546132546312456321456324156324516324
56132456312465321465324165324615326415326145326154326514362514365214356214352614
35216435214635214365124361524361254361245361243561243651423561423516423514623514
263514236514326541362541365241356241352641352461352416352413654213654123

So not only are congratulations due to Robin for settling the conjecture, but a big “thank you” are due to him as well for (hopefully) convincing everyone that this problem is not as easy as it appears upon first glance.

References

1. R. Houston. Tackling the Minimal Superpermutation Problem. E-print: arXiv:1408.5108 [math.CO], 2014.
Tags:
1. August 22nd, 2014 at 12:54 | #1

Thanks for this very nice write-up!

2. August 24th, 2014 at 10:32 | #2

Very interesting! I even wrote a simple program to convince myself — this is indeed a superpermutation for n=6 of length 872. Congratulations Robin!

Curiously, my program found 147 positions within the sequence that do not correspond to permutations (e.g., 123451 starting on 7th position). This means that there are 872 (all positions) – 720 (correct permutations) – 147 (not permutations) – 5 (beginning of the sequence) = 0 repetitions of valid permutations. That is, permutations are never repeated. It is not obvious for me if this must hold in all shortest superpermutations. Robin, do you know if this is always the case?

3. August 24th, 2014 at 17:18 | #3

@Andrey Mokhov That’s an excellent question. I’ve wondered the same thing. I’m pretty sure that permutations are never repeated in any of the minimal superpermutations we know about, but it isn’t obvious to me that must necessarily hold.

4. August 24th, 2014 at 21:36 | #4

@Robin Houston – Yep, I’ll just confirm that there are no repetitions in any of the known minimal (or even formerly smallest but now known not to be minimal) superpermutations. But I also am not aware of a proof that this fact must hold.

5. August 25th, 2014 at 05:39 | #5

@Robin Houston
@Nathaniel
Thank you! Perhaps, a search could be set up to find a 6-superpermutation of length 872, which contains 123456 twice. Due to symmetry, if we find such a superpermutation, it will generate a family of 720 solutions with all possible duplicates. On the other hand, if the search fails then there are no 6-superpermutations of length 872 with duplicates.

By the way, I just checked: Robin’s superpermutation doesn’t contain repetitions of non-permutations either. That is, all contiguous substrings of length 6 are distinct.

6. November 18th, 2014 at 19:26 | #6

Thank you for this post. It’s very interesting and yet comprehensible. Same goes for the article, by the way. He used a nice transformation to interpret the problem as a directed travelling salesman problem, for which powerful solvers exist. Unfortunately no new key insights though..

7. October 6th, 2015 at 04:37 | #7

Hi,

As per the arxiv paper should it be considered that the superpermutation problem is now resolved (in terms of algorithm to find one) ?

Thanks,
S

8. October 8th, 2015 at 06:23 | #8

@Shishir – Nope, it’s only resolved in that we know the original conjecture is false. We still don’t have an algorithm for finding minimal superpermutations, and we still don’t even know how long minimal superpermutations are.

9. October 8th, 2015 at 07:18 | #9

@Nathaniel
@Nathaniel – Thanks for your response. Do you reckon it makes for a good problem in quantum algorithm domain and whether anyone has already come up with one to solve this ?

Cheers,
S

10. October 13th, 2015 at 13:04 | #10

@Shishir – I doubt anyone has already come up with a good algorithm for this problem, since it’s not a particularly famous problem, so I probably would have heard of any substantial progress on it.

I don’t really know if there would be a quantum algorithm that would outperform classical algorithms — I don’t even know if there’s a classical algorithm better than greedy search!