text:
# Difference between revisions of "Interval package"

The interval package provides data types and fundamental operations for real valued interval arithmetic based on the common floating-point format “binary64” a. k. a. double-precision. Interval arithmetic produces mathematically proven numerical results. It aims to be standard compliant with the (upcoming) IEEE 1788 and therefore implements the set-based interval arithmetic flavor.

Warning: The package has not yet been released.

## Motivation

Give a digital computer a problem in arithmetic, and it will grind away methodically, tirelessly, at gigahertz speed, until ultimately it produces the wrong answer. … An interval computation yields a pair of numbers, an upper and a lower bound, which are guaranteed to enclose the exact answer. Maybe you still don’t know the truth, but at least you know how much you don’t know.
—Brian Hayes, DOI: 10.1511/2003.6.484
Standard floating point arithmetic Interval arithmetic
octave:1> 19 * 0.1 - 2 + 0.1
ans =  1.3878e-16

octave:1> x = infsup ("0.1");
octave:2> 19 * x - 2 + x
ans = [-3.1918911957973251e-16, +1.3877787807814457e-16]

Floating point arithmetic, as specified by IEEE 754, is available in almost every computer system today. It is wide-spread, implemented in common hardware and integral part in programming languages. For example, the extended precision format is the default numeric data type in GNU Octave. Benefits are obvious: The performance of arithmetic operations is well-defined, highly efficient and results are comparable between different systems.

However, there are some downsides of floating point arithmetic in practice, which will eventually produce errors in computations.

• Floating point arithmetic is often used mindlessly by developers. [1]
• The binary data types categorically are not suitable for doing financial computations. Very often representational errors are introduced when using “real world” decimal numbers.
• Even if the developer would be proficient, most developing environments / technologies limit floating point arithmetic capabilities to a very limited subset of IEEE 754: Only one or two data types, no rounding modes, …
• Results are hardly predictable. All operations produce the best possible accuracy at runtime, this is how floating point works. Contrariwise, financial computer systems typically use a fixed-point arithmetic (COBOL, PL/I, …), where overflow and rounding can be precisely predicted at compile-time.
• If you do not know the technical details, cf. first bullet, you ignore the fact that the computer lies to you in many situations. For example, when looking at numerical output and the computer says “ans = 0.1,” this is not absolutely correct. In fact, the value is only close enough to the value 0.1.

Interval arithmetic addresses above problems in its very special way and introduces new possibilities for algorithms. For example, the interval newton method is able to find all zeros of a particular function.

## Theory

### Moore's fundamental theroem of interval arithmetic

Let $\displaystyle \mathbf{y} = f(\mathbf{x})$ be the result of interval-evaluation of ${\displaystyle f}$ over a box $\displaystyle \mathbf{x} = (x_1,\ldots{},x_n)$ using any interval versions of its component library functions. Then

1. In all cases, ${\displaystyle \mathbf {y} }$ contains the range of ${\displaystyle f}$ over ${\displaystyle \mathbf {x} }$, that is, the set of ${\displaystyle f(\mathbf {x} )}$ at points of ${\displaystyle \mathbf {x} }$ where it is defined: ${\displaystyle \mathbf {y} \supseteq \operatorname {Rge} (f\vert \mathbf {x} )=\{f(\mathbf {x} )\vert x\in \mathbf {x} \cap \operatorname {Dom} (f)\}}$
2. If also each library operation in ${\displaystyle f}$ is everywhere defined on its inputs, while evaluating ${\displaystyle \mathbf {y} }$, then ${\displaystyle f}$ is everywhere defined on ${\displaystyle \mathbf {x} }$, that is ${\displaystyle \operatorname {Dom} (f)\supseteq \mathbf {x} }$.
3. If in addition, each library operation in ${\displaystyle f}$ is everywhere continuous on its inputs, while evaluating ${\displaystyle \mathbf {y} }$, then ${\displaystyle f}$ is everywhere continuous on ${\displaystyle \mathbf {x} }$.
4. If some library operation in ${\displaystyle f}$ is nowhere defined on its inputs, while evaluating ${\displaystyle \mathbf {y} }$, then ${\displaystyle f}$ is nowhere defined on ${\displaystyle \mathbf {x} }$, that is ${\displaystyle \operatorname {Dom} (f)=\emptyset }$.


text:
## Probability in the North East day

#### 16 February 2018

University of Leeds.

Organizer: Martín López-García.

These people attended the meeting.

## Programme

12:30–13:15
Lunch
13:15–14:00
Thomas House (University of Manchester)
In epidemiology, we want to count individuals in different disease states, and yet the non-linear pure-jump processes that we might want to use for modelling and inference are often highly computationally demanding, or even intractable. I will consider a set of approximating stochastic processes to these full models.
14.00–14.45
István Zoltán Kiss (University of Sussex)
The emergence of networks as a modelling paradigm has allowed to capture and model contact with an unprecedented level of detail, leading to a major shift in how epidemics are investigated. However, the propensity of contacts to cluster (i.e., neighbours of a node being also likely to be connected) continues to pose major modelling and analytical challenges. Apart from some theoretical results on idealised networks there is a limited number of general theoretical results. Mean-field models, such as pairwise models, have been used successfully in approximating the average behaviour of epidemics on networks with no clustering and have led to significant results such as an analytical epidemic threshold and final epidemic size for susceptible-infected-recovered (SIR) epidemics. While equivalents of the pairwise model for clustered networks are available, there are limited analytic or semi-analytic results. In this talk I show that it is possible to use the correlation structure at early times to work out a semi-analytic epidemic threshold using pairwise models for clustered networks. Furthermore, I present a systematic comparison between two pairwise models for clustered networks and the pairwise model for networks with no clustering. This comparison shows that for SIR epidemics, these models only differ over a limited range of the average degree and transmission rates. Although clustering in densely connected networks has little effect on epidemics, especially for the simplest epidemic dynamics, its effect may be more profound for dynamics such as complex contagion where the higher-order structure of the network, i.e., how clustering is achieved, has a more marked effect on the dynamics unfolding on it. This may indicate that choosing models for clustered networks may strongly depend on the dynamics considered.

This is joint work with Rosanna C. Barnard, Luc Berthouze, Nicos Georgiou, and Simon L. Péter.
14:45–15:15
Bemsibom Toh (Heriot-Watt University)
The classical many-sources asymptotic regime of the single server queue is widely known and exhaustively studied. However, it is limited in that it does not enable the study of different traffic regimes, and how they interact with each other.

In this talk, we present a new paramerization of the many-sources asymptotic regime, indexed by $\alpha$ and $\beta$. The parameter $\alpha$ is used to control the threshold size scaling, while the parameter $\beta$ controls the excess service rate above the arrival rate. We also present new large deviations bounds for threshold overflow probabilities for different values of $\alpha$ and $\beta$.
15:15–15:45
Tea and coffee
15:45–16:30
Maria Nowicka (University of Leeds)
The aim of this talk is to show an alternative to the analysis of the chemical master equation (CME) when studying biological systems from a stochastic point of view. In particular, we propose to analyse probabilistic descriptors that allow us to obtain information of the process under study, sidestepping the analysis of the CME. We illustrate this approach in a stochastic model for the interaction between the vascular endothelial growth factor receptor 2 (VEGFR-2), with the vascular endothelial growth factor VEGF-A in human vascular endothelial cells. Receptor VEGFR-2 and ligand VEGF-A interact through their binding, forming signalling bound complexes on the cell surface. The interest here is in the analysis of the time scales to reach any signal threshold. We quantitatively measure this time as a random variable that can be identified as a first-passage time in the theory of stochastic processes, and the computation of its different order moments can be reduced to the solution of a series of systems of linear equations, that can be efficiently solved through a matrix formalism. Our methodology is illustrated by carrying out a series of numerical results, where we focus on the effect that different hypothesis about signal formation have on this time.
16:30–17:15
Elizabeth Buckingham-Jeffery (University of Manchester)
I will present a flexible framework for deriving and quantifying the accuracy of Gaussian process approximations to non-linear stochastic individual-based models of infectious diseases. This will be demonstrated with a simple infectious disease model, although it is straight-froward to extend to more complex models. I will then show how it can be used with real outbreak data on the number of new cases of norovirus on a cruise ship to quickly infer the underlying parameters of the epidemiological model and the unobserved processes.

format: plain


text:
An error was encountered while trying to add the item to the cart. Please try again.
Copy To Clipboard
Successfully Copied!
Generalized Dyson Series, Generalized Feynman Diagrams, the Feynman Integral and Feynman’s Operational Calculus

Available Formats:
Electronic ISBN: 978-1-4704-0767-4
Product Code: MEMO/62/351.E
List Price: $21.00 MAA Member Price:$18.90
AMS Member Price: $12.60 Click above image for expanded view Generalized Dyson Series, Generalized Feynman Diagrams, the Feynman Integral and Feynman’s Operational Calculus Available Formats:  Electronic ISBN: 978-1-4704-0767-4 Product Code: MEMO/62/351.E  List Price:$21.00 MAA Member Price: $18.90 AMS Member Price:$12.60
• Book Details

Memoirs of the American Mathematical Society
Volume: 621986; 78 pp
MSC: Primary 81; Secondary 58;

• Chapters
• 0. Introduction and preliminaries
• 1. A simple generalized Dyson series ($\eta = \mu + \omega \delta _\tau$)
• 2. The generalized Dyson series
• 3. Examples of perturbation expansions
• 4. Stability results
• 5. Generalized Feynman diagrams
• 6. The Banach algebra of functionals. Connections with Feynman’s operational calculus
• Requests

Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Volume: 621986; 78 pp
MSC: Primary 81; Secondary 58;
• Chapters
• 0. Introduction and preliminaries
• 1. A simple generalized Dyson series ($\eta = \mu + \omega \delta _\tau$)
• 2. The generalized Dyson series
• 3. Examples of perturbation expansions
• 4. Stability results
• 5. Generalized Feynman diagrams
• 6. The Banach algebra of functionals. Connections with Feynman’s operational calculus
Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.


text:
# All Questions

164 views

### In cryptographic protocols, what protects against an attacker dropping messages?

In some cryptographic protocols I have seen messages protected for confidentiality, authenticity, replaying attacks, reordering attacks, etc. What protects a protocol from an attacker in a ...
85 views

### Corporate PKI - SHA1 deprecation [closed]

Here is the context. Suppose you have a corporate PKI with : AC_Root (offline in safe store - SHA1 signature) SubRootA ans SubrootB (offline in safe store - SHA1 signature) SubSubRootC, ...
425 views

### RFC 6979 - Why not simply hash the message & the private key for deterministic ECDSA?

Why go through the trouble of using the HMAC_DRBG process, instead of simply hashing [message | private key] to calculate $k$ for deterministic ECDSA? If the ...
130 views

### block cipher algorithms with variable block lengths

Rijndael supports block lengths of 128, 192 and 256. AES does not but Rijndael does. What other algorithms support variable block lengths? Or is Rijndael unique in that regard?
53 views

### transforming RC2 keys to have effective minimum length in implementations with fixed effective lengths

mcrypt's implementation of RC2 has a fixed effective length of 1024 bits, however, it is possible to simulate keys with effective lengths between 1-1024 by doing something like this: ...
96 views

### Does SHA-1 hash have quasi commutative property? [closed]

Although I have tested with a program and found negative answer, I want to be sure.
3k views

### Why there are limitations on using encryption with keys beyond certain length?

I am writing a java program to encrypt a message using 256-bit AES encryption, but I am getting illegal key size error, I have read that I have to use some JCE ...
82 views

### Issue about randomness : what if random looks “human” ? [closed]

I read a lot of stuffs about entropy/randomness. But what if a random generator (either digits or strings) once output a "human" patern ? I know it is very unlikely to happen, but if a random code ...
125 views

### Is there an alternative AES schedule?

I'm currently reversing an AES implementation for disk encryption. The odd thing I'm stumbled about is a key schedule where the encryption round keys are not the same as the decryption round keys (in ...
198 views

### Verifying DER encoded DSA/ECDSA signature with extra content?

Having a DSA/ECDSA signature which is supposed to be DER encoded as an ASN.1 sequence of $r$ and $s$ (as described in the RFC), and being given some bytes which are ...
295 views

### secure embedded/microcontroller crypto using AES-ctr with hmac-sha2

The embedded device is a low-power 8-bit microcontroller (memory usage is constrained to about 10kb code, 1kb ram). As the device is battery-powered and manual service should be minimal, more powerful ...
289 views

### Finding Elliptical curve points and encoding text using them

I recently got into learning Elliptical curve cryptography and are currently building a project in C#. Everything is working well so far, I can encode and decode points, and thanks to this forum I ...
72 views

### How to establish if a string contains a message

If you have a string S, then the string can be composed of four things: cleartext 'random' data encrypted data compressed or otherwise non-encrypted, but modified, cleartext If you want to see if ...
101 views

### Does MD5 hash have quasi commutative property? [duplicate]

I am implementing a one-way accumulator using MD5 hash, wondering wheather it has quasi commutative property or not.
1k views

### How Brittle Are LCG-Cracking Techniques?

There are published techniques for cracking LCGs, but to my eye those techniques seem very brittle — very minor changes can add nonlinearity that renders techniques like the LLL algorithm unusable. ...
443 views

### Collision in Merkle–Damgård without a collision in compression function

Is it possible to find a collision in Merkle–Damgård just by omitting the extra one bit that is appended to each input without having a collision in compression function?
93 views

### Is the Vigenère Cryptosystem malleable? [closed]

Is the Vigenère Cryptosystem malleable, and how can we prove that it is (or it is not) malleable?
81 views

### Meaning of Multiplicative Group to the power n i.e. Z^n [closed]

What does $Z_q^n$ mean in this notation?      References: on the 2nd paragraph of page: http://en.wikipedia.org/wiki/Learning_with_errors
269 views

### Maximum length in bits of the product n=pq

If p and q are two 1024-bit prime numbers, would the maximum length in bits of product $n=pq$ be ${1024}^2$ or $2^{1024}$? I think it is ${1048576}={1024}^2$? Also, would the least significant bit ...
97 views

### can you suggest any applicayion for implementing threshold homomorphic encryption cryptosystem(Paillier cryptosystem) [closed]

I want to implement one project in multi party homomorphic encryption using paillier. Can you suggest any application for implementation.
117 views

### RSA OAEP: prevention of partial decryption of ciphertexts

I'm trying to understand RSA encryption (as a beginner in cryptography). go on this wiki page http://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding scroll down to the 2 numbered points: ...
102 views

### Repeatedly using same key on different plaintexts

Symmetric encryption: Does using the same key over and over again introduce a vulnerability? Meaning, if I transmit a different piece of plaintext encrypted with the same key every day, will an ...
85 views

### Minimum number of independent trials needed to detect a bias [closed]

Suppose, I suspect that the probability of occurrence of a particular bit as $0$ is $.558$. Since, it is not $.5$, so this is possibly a bias. Now, my question is: What is the minimum number of ...
260 views

### Computation indistinguishability questions

The definition I have is: Two probability ensembles $X = \{X_n\}_{n \in \mathbf{N}}$ and $X = \{Y_n\}_{n \in \mathbf{N}}$ are computationally indistinguishable if for every probabilistic ...
206 views

### CoAP authentication using DTLS

what is the meaning of this notation ?? AES{Yi, (Yi XOR Ki | nonce1)} https://tools.ietf.org/html/draft-bhattacharyya-core-coap-lite-auth-00
436 views

### Elliptical curve cryptography key generation time

I am currently trying to learn more about Elliptical curve crypthography and have finally started to get things working and undestanding the different pieces. I've written a small project in C# and ...
407 views

### Sharing an encrypted file between a group of people

Is there any way to share an encrypted file with a group? In the other words, can I encrypt a file with a public key so that each person in a group decrypt it with his/her private key? Is there any ...
90 views

### simulating rc4-256 with rc4-128

OpenSSL supports rc4 with 128-bit keys and rc4 with 40-bit keys. It does not support rc4 with 256-bit keys. My question is... is it possible to modify the state of the pseudo-random generation ...
136 views

### what are multi-primes and how are they different from semiprimes?

I came to know of semiprimes recently. The simplest explanation of semiprimes is you take any two prime numbers and you multiply them, say 3*11 = 33 in which case 33 would be a semiprime. The numbers ...
295 views

### Cracking plain RSA by factoring the modulus n

This is the setup: I have both public and private keys of one "instance" of RSA. And I have only the public key of another RSA cryptosystem, but this system has the same modulus as the first one. I ...
167 views

### Where to store the file extension to retrieve it correctly after decryption

I am using Java to write AES-256 to encrypt various files with different extension, the problem is, where am I suppose to store the file extension so the if the data is decrypted, the file extension ...
91 views

### Less known hash functions producing 128 bit hash [closed]

Good day. While reversing a malware I stumbled upon a function producing 16 byte hash. I tried to determine which one is that by checking every function from wiki. Nothing fits. So, there are two ...
80 views

### Efficient proof of knowledge using Wegman-Carter hash

A verifier wants to ensure, with only little exchange of data with other systems, that a large block of data $M$ that the verifier holds is also available to some other system(s). It is not an ...
84 views

### Inverse of a function $f_k(x) := f (x ⊕ k) ⊕ k$

$f : \{0, 1\}^4 → \{0, 1\}^4$ Given a function $f_k(x) := f (x ⊕ k) ⊕ k$, what is the inverse function $f_k^{-1}$? I could not figure out how this would be done. Thanks.
138 views

### El gamal correctness

I tried to find online for the correctness of El-Gamal, but I couldn't find any good resource that will teach me how to show the correctness of El-Gamal, could any body show me how is it done?
103 views

### Recovering El Gamal secret key from signatures [duplicate]

Assume out of a set of ElGamal signatures, I've discovered that two have the same y i.e. $signature_{1}$ on $m_{1}$ = $(y,s_{1})$ and $signature_{2}$ on $m_{2}$ = $(y,s_{2})$. The public keys for ...
98 views

### What is the difference between IND-CCA2 and NM-CCA2? And how does one imply another? [closed]

Is there any proof that shows the equivalence of these two?
180 views

### Building a pad for OTP on-the-fly with Diffie-Hellman

Through repeated DH attempts, could Alice and Bob build a large random key for use as a one-time pad? My intuition is that this protocol would be as hard as breaking DH (discrete logarithm).
144 views

### Private Information Retrieval--Is it still theoretical?

Are there any real world products in which private information retrieval techniques are used?(a data hosting server oblivious of which data item was fetched from it?)If not what are the major barriers ...
246 views

### Recover a secret message in a .wav file [closed]

First, I apologize for my english, I'll do my best. On my computer, I got a .wav audio file that hides a secret message. I want to recover that message. But I'm stuck and I need your help :). My ...
469 views

### How does hash function in Elgamal signature scheme prevent existential forgery attack?

I have heard that hashing the message M prevents an existential forgery attack. I was wondering how.
278 views

### Real life systems that use concepts of crypto computing [closed]

Are there any working cloud/internet solutions/products that operates on encrypted data such as systems using homomorphic encryption, secure multiparty computation, electronic voting, private ...


text:
# Math Help - vector questions

1. ## vector questions

find the co-ordinates of the point of intersection of the lines whose equations are, $\frac{x}{1}= \frac{y}{3}=\frac{z}{2}\ and \ \frac{x-2}{1}=\frac{y-3}{4}=\frac{z-4}{2}$

2. Originally Posted by ashes
find the co-ordinates of the point of intersection of the lines whose equations are, $\frac{x}{1}= \frac{y}{3}=\frac{z}{2}\ and \ \frac{x-2}{1}=\frac{y-3}{4}=\frac{z-4}{2}$
Re-write the equations:

$\left|\begin{array}{l}x = t\\y=3t\\z=2t\end{array}\right.$ ..... and ..... $\left|\begin{array}{l}x=s+2\\y=4s+3\\z=2s+4\end{ar ray}\right.$

Solve the system of simultaneous equations for s, t:

$\left|\begin{array}{l}t=s+2\\3t=4s+3\\2t=2s+4 \end{array}\right.$

I've got: (s, t) = (3, 5)

Therefore the point of intersection is P(5, 15, 10)


text:
# How to determine transitivity and intransitivity of this relation?

I am having trouble finding if the following relation is transitive or intransitive. I would be very thankful if someone could help me out by explaining transitivity and its rules with regard to this example,

$$R = \{ (1,3),(1,1),(3,1),(1,2),(3,3)(4,4) \} .$$

Thanks.

-
Beware terminology: You mean whether the relation you show is transitive, not whether the set is. (There is something called "transitive" for sets in general, but that is something almost entirely different from what you're speaking about here). – Henning Makholm Nov 4 '11 at 15:07
Is your problem that you don't know what "transitive" means, or is it that you have a definition, but don't understand how to apply it? If the latter, then please quote the definition and share some thoughts about how it might apply to your example. – Henning Makholm Nov 4 '11 at 15:10

A relation on a set is transitive if, when we have (a,b) and (b,c), we have also (a,c).

So here, we just check some cases. 4 is on on its own - so we don't really care about 4.

Let's look at 1 and 3. We have (1,3) and (3,1) - do we have (1,1)? Yes, we do. Similarly, we have (3,1) and (1,3), and we also have (3,3). These are all the relations on 3.

But then we consider 1 and 2...

-
$(1,2)$ is there but $(2,1)$ is not there, so its intransitive, right? – Fahad Uddin Nov 4 '11 at 15:30
@Akito, no, you're confusing that with symmetry. – Henning Makholm Nov 4 '11 at 15:35
@HenningMakholm: So what to do with $(1,2)$? It does not satisfy the condition.. – Fahad Uddin Nov 4 '11 at 16:37
@HenningMakholm: I got the point that you made but there is no pair for $(1,2)$ – Fahad Uddin Nov 4 '11 at 16:47
@Akito, a single pair cannot possibly fail to satisfy the condition. The condition is "when we have (a,b) and (b,c) ...", so the only way the condition can fail to hold is if we can find two pairs such that one is (a,b) and the other is (b,c) yet there is no (a,c) in the relation. – Henning Makholm Nov 4 '11 at 17:02

Transitivity says that if you have $aRb$ and $bRc$ you also have $aRc$. When your relation is a given set of pairs, you have to look through and see if it is true. If $a=2$, there is no $b$ such that $aRb$, so we satisfy the requirement. If $a=4$, we must have $b=4$ and then $c=4$ and we do get $aRc$. When $a$ is $1$ or $3$, you have more possibilities for $b$ and have to follow each path to see where it leads.

-

here 3R1 and 1R2 but it is false that 3R2 so it is not transitive

-


text:
# Nested equilateral triangles

Let triangle $$ABC$$ is an equilateral triangle. Triangle $$DEF$$ is also an equilateral triangle and it is inscribed in triangle $$ABC \left(D\in BC,E\in AC,F\in AB\right)$$. Find $$\cos\measuredangle DEC$$ if $$AB:DF=8:5$$.

Firstly, I would be very grateful if someone can explain to me how I am supposed to draw the diagram. Obviously I have made it by sight.

Let $$\measuredangle DEC=\alpha$$. We can note that $$\triangle AEF \cong \triangle BFD \cong CDE$$. This is something we can always use in such configuration. So $$AE=BF=CD,$$ $$AF=BD=CE.$$ Let $$AB=BC=AC=8x$$ and $$DF=DE=EF=5x$$. If we denote $$CD=y,$$ then $$CE=AC-AE=AC-CD=8x-y$$. Cosine rule on $$CED$$ gives $$25x^2=(8x-y)^2+y^2-2y\cos60^\circ(8x-y)$$ which is a homogenous equation. I got that $$\dfrac{y}{x}=4\pm\sqrt{3}.$$ Now using the sine rule on $$CED$$ $$\dfrac{CD}{DE}=\dfrac{\sin\alpha}{\sin60^\circ}\Rightarrow \sin\alpha=\dfrac{\sqrt{3}}{10}\cdot\dfrac{y}{x}=\dfrac{4\sqrt3\pm3}{10}.$$ Now we can use the trig identity $$\sin^2x+\cos^2x=1$$ but it doesn't seem very rational. Can you give me a hint? I was able to find $$\sin\measuredangle DEC$$ in acceptable way, but I can't find $$\cos\measuredangle DEC$$...

• @MathLover, edited. I am sorry. – Katherine Jan 25 at 19:53

Here I will show how you can draw the figure. The calculations that follow are somewhat similar to other answers.

We can build triangle $$DEF$$ by scaling down triangle $$ABC$$ and rotating it around its centroid $$G$$ by some angle $$\alpha$$.

Notice the hatched triangle $$DHG$$. This is a right triangle with sides: $$GH = \frac13 AH =\frac{4}{12} AH$$ $$DG = \frac23 DY = \frac23 \times \frac58 AH = \frac{5}{12} AH$$ $$HD = \sqrt{DG^2 - GH^2} = \frac{3}{12} AH$$ It seems the designer of the problem intentionally used the ratio $$\frac58$$ to lead us to the $$3-4-5$$ right triangle!

Anyway, Now we are able to locate point $$D$$ on $$BC$$. It is at distance $$\frac14 AH$$ from point $$H$$ , the midpoint of BC. We can similarly locate points $$E$$ and $$F$$ , hence constructing triangle $$DEF$$.

Now, as for calculations, note that $$\widehat{DEC}=120^o - \alpha$$ and that $$\widehat{DGH}=60^o - \alpha$$. So $$\widehat{DEC}=60^o+\widehat{DGH}$$ . Therefore: $$\cos \widehat{DEC} = \cos (60^o+\widehat{DGH}) = \cos60^o \cos \widehat{DGH} - \sin60^0 \sin \widehat{DGH}$$ $$= \frac12 \times \frac45 - \frac{\sqrt 3}{2} \times \frac35 = \frac{4-3\sqrt3}{10}$$ Note that when locating point $$D$$ we have two options, say, above and below $$H$$. The above calculations are for the option shown in the figure, where $$D$$ is selected below $$H$$. Alternatively, we could select $$D$$ to be above $$H$$, and respectively have $$E$$ below $$K$$. The interested reader can verify that in that case $$\widehat{DEC}$$ would be $$\alpha$$. And $$\; \cos\alpha \;$$ can be calculated similar to above. $$\cos \alpha = \cos (60^o-\widehat{DGH}) = \cos60^o \cos \widehat{DGH} + \sin60^0 \sin \widehat{DGH} = \frac{4+3\sqrt3}{10}$$

Note that there are two distinct solutions given the conditions in the problem. This is because there are two admissible orientations of $$\triangle DEF$$: one in which $$AF > BF$$, and one in which $$AF < BF$$. We can understand this by noting that since $$\triangle DEF$$ and $$\triangle ABC$$ share the same center, the circumcircle of $$\triangle DEF$$ will intersect $$\triangle ABC$$ at six points, unless the side length of $$\triangle DEF$$ is less than or equal to half the side length of $$\triangle ABC$$ (in which case there will be either exactly three intersection points in the tangent case, or zero), or greater than or equal to the side length of $$\triangle ABC$$.

A simple way to solve for the required angle is to place the triangle on a coordinate system, say with $$A = (0,0)$$, $$B = (8,0)$$, $$C = (4, 4 \sqrt{3})$$, and let $$F = (x,0)$$ for some $$0 \le x \le 8$$. Then $$E = \left(\frac{8-x}{2}, \frac{(8-x)\sqrt{3}}{2}\right).$$ We then require $$EF = 5$$, or $$25 = \left(x - \frac{8-x}{2}\right)^2 + \left(\frac{(8-x)\sqrt{3}}{2}\right)^2 = 3x^2 - 24x + 64.$$ Consequently $$x = 4 \pm \sqrt{3}$$ and depending on which root is chosen, $$\angle DEC$$ can be determined through a straightforward application of the Law of Sines.

• I was partway through putting together a Geogebra construction of the triangle using the "guess the value of $x$" method. With that in mind I'll just link it here: geogebra.org/calculator/wwf7p4nc. Note that $x=4-\sqrt{3}\approx 2.268$ indeed gives a triangle of the proper size. – Semiclassical Jan 25 at 21:01

WLOG, $$AB = 8, DF = 5$$. Say $$\angle DEC = \theta$$

If $$CD = x$$ then $$CE = 8 - x$$

Applying sine law in $$\triangle CDE$$,

$$\displaystyle \frac{\sin 60^0}{5} = \frac{\sin \theta}{x} = \frac{\sin(60^0+\theta)}{8-x}$$

From first two, we have $$\sin \theta = \frac{x \sqrt3}{10}$$

From first and third, $$\sin 60^0 \cos \theta + \cos 60^0 \sin\theta = \frac{4\sqrt3}{5} - \frac{x \sqrt3}{10}$$

$$\implies \cos\theta = \frac{8}{5} - \frac{3x}{10}$$

Applying $$sin^2\theta + \cos^2\theta = 1$$, we get

$$x^2 - 8x+\frac{39}{3} = 0 \implies x = 4 \pm \sqrt3$$

So, $$\cos\theta = \frac{4 \mp 3\sqrt3}{10}$$ (please note $$\pm$$ for $$x$$ and corresponding $$\mp$$ for $$\cos \theta$$)

You may calculate $$\cos\alpha$$ directly. Per the sine rule for $$\triangle CDE$$ $$\frac{\sin \alpha }{CD}= \frac{\sin (120-\alpha) }{AB-CD}= \frac{\sin 60 }{DE}$$ Eliminate $$CD$$ to get $$\frac{AB}{DE}\sin 60 = \sin\alpha + \sin(120-\alpha)=2\sin 60\cos(60-\alpha)$$ which leads to $$\cos(60-\alpha)=\frac45$$. Then, $$\cos\alpha = \cos(60\pm\cos^{-1}\frac45) =\frac12\cdot \frac45\mp\frac{\sqrt3}2\cdot \frac35 =\frac{4\mp 3\sqrt3}{10}$$

• Thank you for the response! It seems cool, but we still haven't studied how to solve trigonometric equations. – Katherine Jan 26 at 9:05
• Can I somehow find $\cos\measuredangle CED$ using what I found $\dfrac{y}{x}=4\pm\sqrt{3}$? – Katherine Jan 26 at 9:11
• @nicoledobreva - you can then use the cosine rule to calculate $\cos \angle CED$ fron the ratio $y/x$ – Quanto Jan 26 at 16:59
• It is really easier if we assume that $AB=8$ and $DF=5$. We don't need $x$ then. Can I ask you why can we do that? Can we always use this method, e.g. if we have $a:b=c:d$ can we always assume w.l.o.g. that $a=c$ and $b=d$? – Katherine Jan 26 at 17:00
• Can I ask you how do we eliminate $CD$? – Katherine Jan 27 at 20:40

As others have done, I'll assume $$AB=8,DF=5$$ without loss of generality. Then equilateral triangles $$\triangle ABC$$ and $$\triangle DEF$$ have area $$(\sqrt{3}/4)AF^2 = 16\sqrt{3}$$ and $$(\sqrt{3}/4)DF^2=(25/4)\sqrt{3}$$ respectively. Since the triangles $$\triangle FAE,\triangle DBF, \triangle ECD$$ are all congruent, they must each have area $$\frac{1}{3}\left(16\sqrt{3}-\frac{25}{4}\sqrt{3}\right)=\frac{13\sqrt{3}}{4}.$$ But each triangle has a 60-degree base angle, so we can also write the area of $$\triangle FAE$$ as

$$\frac12 AF\cdot AE \cdot \sin 60^\circ$$

Since $$AE=AC-EC=8-AF$$, this becomes $$\frac12 AF(8-AF)\frac{\sqrt{3}}{2}= \frac{13\sqrt{3}}{4}\implies AF(8-AF)=13$$ with $$x=4\pm \sqrt{3}$$ as solutions. As a minor variation on the other approaches, we may then use the law of cosines on triangle $$\triangle CED$$ to write

$$CD^2=CE^2+ED^2-2CE\cdot ED\cos\measuredangle DEC$$ and therefore

\begin{align} \cos\measuredangle DEC &=\frac{CE^2+ED^2-CD^2}{2CE\cdot ED}\\ &=\frac{(4\pm \sqrt{3})^2+5^2-(4\mp \sqrt{3})^2}{2(5)(4\mp \sqrt{3})}\cdot \frac{4\mp \sqrt{3}}{4\mp \sqrt{3}}\\ &=\frac{(25\pm 16\sqrt{3})(4\mp \sqrt{3})}{130}\\ &=\frac{52\pm 39\sqrt{3}}{130}\\ &=\frac{4\pm 3\sqrt{3}}{10} \end{align} as others have obtained.

• Thank you for the response! I don't understand the first part of your solution (probably you are using some area formulas that I haven't studied). I am new to trig, so I really don't know many things. Can we somehow use what I found - $\dfrac{y}{x}=4\pm\sqrt{3}$ to find $\cos\measuredangle CED$? – Katherine Jan 26 at 9:16
• @nicoledobreva To be honest, I looked up the area formulas for equilateral triangles. But these are just applications of the area formula $A=\frac12 ab\sin\theta$ to the case $a=b$ and $\theta=60^\circ.$ As for your work, I’ve effectively assumed $x=1$ and solved for $8-y=4\pm \sqrt{3}$, in agreement with your results. To finish you can combine your results with either law of sines (as others have) or law of cosines (as I have) to get the desired cosine. – Semiclassical Jan 26 at 14:37


text:
# Particular function communication complexity computation

Consider a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then communication complexity of function is $\Omega(n)$. This is claim $4.23$ in Jukna's book. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with atleast $r$ number of $n$ of $0/1$ vectors $x$ each of Hamming weight $1$, then is communication complexity of function $\Omega(r)$? Could this possibly have truth?

There is a cheap lower bound of $\Omega(r)$ obtained by reduction. Suppose for simplicity that the $r$ dIstinguished coordinates are the first $r$. Let $g(x_1,\ldots,x_r) = f(x_1,\ldots,x_r,0,\ldots,0)$. Your condition on $f$ implies that $g$ satisfies Jukna's condition on $g$, so $g$ has communication complexity $\Omega(r)$. Any protocol for $f$ also works for $g$, so we get a lower bound of $\Omega(r)$ for $f$.
• Thank you. I am sorry $f(\underbrace{0,\dots,0}_{r\text{ times}},\dots,\underbrace{1,\dots,1}_{r\text{ times}},\dots,\underbrace{0,\dots,0}_{r\text{ times}})$ where each sequence of $0/1$ is $r$ in length will have no guarantee to be $1$ since $(\underbrace{0,\dots,0}_{r\text{ times}},\dots,\underbrace{1,\dots,1}_{r\text{ times}},\dots,\underbrace{0,\dots,0}_{r\text{ times}})$ does not have Hamming weight $1$. Am I missing something? – T.... Mar 7 '15 at 22:12
• It is $g$ that satisfies the Hamming weight 1 condition. – Yuval Filmus Mar 7 '15 at 23:23
• I understand that input to $g$ is of Hamming weight $1$. However, you are expanding input aritifically by repeating $0$s/$1$s. $f$ satisfies $f(x)=1$ when $|x|_{HAMM}=1$ with atmost $r<n$ such $x$ vectors. Expanded input to $f$ is no longer hamming weight $1$. – T.... Mar 7 '15 at 23:26
• Ah, now I understand your question. A similar reduction would work for your actual question. Pick the $r$ good coordinates and fix the rest to zero. Then you get an $\Omega(r)$ lower bound. – Yuval Filmus Mar 7 '15 at 23:30


text:
# Prove that $\sqrt{3}+ \sqrt{5}+ \sqrt{7}$ is irrational [duplicate]

How can I prove that $\sqrt{3}+ \sqrt{5}+ \sqrt{7}$ is irrational?

I know that $\sqrt{3}, \sqrt{5}$ and $\sqrt{7}$ are all irrational and that $\sqrt{3}+\sqrt{5}$, $\sqrt{3}+\sqrt{7}$, $\sqrt{5}+\sqrt{7}$ are all irrational, too. But how can I prove that $\sqrt{3}+ \sqrt{5}+ \sqrt{7}$ is irrational?

## marked as duplicate by Watson, Namaste, Gibbs, Lord Shark the Unknown, Lord_FarinNov 28 '18 at 19:17

Suppose $\sqrt{3}+\sqrt{5}+\sqrt{7} = r$ for some rational $r$. Then, $$(\sqrt{3}+\sqrt{5})^2 = (r-\sqrt{7})^2 \implies 8+2\sqrt{15} = 7+r^2-2r\sqrt{7}$$ So, $$1-r^2+2\sqrt{15} =-2r\sqrt{7}$$ Let $1-r^2 = k$, which will be a rational number. So, $$(k+2\sqrt{15})^2 = k^2+ 60+4k\sqrt{15} = 28r^2$$ The LHS is irrational while the RHS is rational. Hence, we have a contradiction.

You can easily show (probably you have already done so) $\sqrt{5},\sqrt{7} \in \mathbb Q(\sqrt{5}+\sqrt{7})$.

If your sum would be rational, we would deduce $\sqrt{5},\sqrt{7} \in \mathbb Q(\sqrt{5}+\sqrt{7}) \subset \mathbb Q(\sqrt{3})$, clearly a contradiction.

Assume $$\sqrt{3}+ \sqrt{5}+ \sqrt{7}= \frac{a}{b}$$ for some integers $a,b$. Multiblying both sides by $\sqrt{3}+ \sqrt{5}- \sqrt{7}$ yields $$(\sqrt{3}+\sqrt{5})^2 - 7 = \frac{a(\sqrt{3}+ \sqrt{5}- \sqrt{7})}{b}=\frac{a\left(a/b-2\sqrt{7}\right)}{b} \\ 2\sqrt{15}+8-7=\frac{a^2/b-2a\sqrt{7}}{b} \\ 2b\sqrt{15} = \frac{a^2}{b}-2a\sqrt{7}-b \\ 60b^2=\frac{a^4}{b^2}+28a^2+b^2-\frac{4a^3\sqrt{7}}{b}+4ab\sqrt{7}-2a^2 \\ 59b^2-26a^2-\frac{a^4}{b^2}=4a\sqrt{7}\left(b-\frac{a^2}{b}\right).$$ We can divide both sides by $4a(b^2−a^2)=4a(b-a)(b+a)$ because $a$ can't be $0$ by definition, $b+a$ is a positive integer and $b−a$ can't be $0$ because that would imply $a/b=1$, which is impossible. Thus we get $$\frac{b\left(59b^4-26a^2b^2-a^4\right)}{4a(b^2-a^2)}=\sqrt{7},$$ contradiction.

• Contradiction only if the numerator and the denominator of that last fraction are not zero... – lhf Mar 23 '15 at 19:18
• If that last fraction is undefined, then the RHS is too, but it isn't; why wouldn't that be a contradiction anyway? – Vincenzo Oliva Mar 23 '15 at 19:30
• Strictly speaking, you only have ${b\left(59b^4-26a^2b^2-a^4\right)}=\sqrt{7}\cdot{4a(b^2-a^2)}$ – lhf Mar 23 '15 at 19:32
• We can divide both sides by $4a(b^2-a^2)$ because $a$ can't be $0$ by definition, $b+a$ is a positive integer and $b-a$ can't be $0$ because that would imply $a/b=1$, which is impossible. Or am I missing something? – Vincenzo Oliva Mar 23 '15 at 19:35
• That's much better. Consider adding this to your answer. – lhf Mar 23 '15 at 19:37

Let $\alpha=\sqrt{3}+ \sqrt{5}+ \sqrt{7}$.

Then $\alpha$ is a root of $x^8-60 x^6+782 x^4-3180 x^2+3481=0$. Since this is a monic polynomial with integer coefficients, the rational root theorem tells you that $\alpha$ is either irrational or an integer.

Now

$\quad 1.7 < \sqrt 3 < 1.8$

$\quad 2.2 < \sqrt 5 < 2.3$

$\quad 2.6 < \sqrt 7 < 2.7$

gives

$\quad 6.5 < \alpha < 6.8$

which proves that $\alpha$ is not an integer.

We can avoid even these fine estimates: if $\alpha$ is an integer then it must divide $3481=59^2$, but clearly $1 < \alpha < 3\sqrt 7 < 9 < 59$.

According to Galois, if $\sqrt3 +\sqrt5+\sqrt7$ is rational, then it must be invariant after changing the sign of any or all of the square roots. But the expression is clearly positive, so it cannot be equal to its negative.

• Please clarify. $\sqrt{4}$ is rational, but we generally don't say $\sqrt{4} = -\sqrt{4}$. – DanielV Mar 23 '15 at 21:08
• In this case, the Galois transformations involve changing the signs of any or all of the roots of the three primes. Total of eight transformations, including unity. Your suggestion is not included. – Bill Kleinhans Mar 24 '15 at 3:33


text:
## Introduction

Light causes changes in the chemical and electronic states of photo-responsive materials, thereby imparting functionality. Such materials have been studied for many years. Applications of light-induced functions include solar cells, photoconductors, photoinduced insulators, photochromism, photocatalysis, solidification and viscosity changes due to light irradiation, and light-induced magnetism1,2,3,4. Among them, both photochromism and photocatalysis are useful and have been now widely applied in society5,6,7. Photochromism is the reversible color change caused by light irradiation. Photocatalysis can generate hydrogen by decomposing water and organic materials by light irradiation. As is well known, TiO2 is typical photocatalysis and which has been used in a wide range of applications such like coating agents to decompose stains on exterior walls6,7. Photocatalysts in particular hold promise also in public health for antibacterial and antiviral applications.

## Experimental and methods

### Synthesis methods

PHI was obtained by the thermal treatment of the precursor melon. Melon was synthesized in a quartz tube placed in a commercial tube furnace (Koyo Thermo Systems Co., Ltd., KTF035N1) under a nitrogen atmosphere (purity: 99.99995%)18. All quartz tubes and boats were pre-annealed to remove contaminants, and NH3 and CS2 gas were removed using a fixed flow rate of N2 gas at 200 mL min−1 before each synthesis.

To synthesize melon, melamine (3.0 g, purity: 99.0% Wako Pure Chem., Ind., Ltd., 139-00945) was placed in the bottom of a quartz tube (Nichiden-Rika Glass Co., Ltd., P-18SM) and the tube was capped with aluminum foil with a central pinhole ~ 0.6 mm in diameter. The aluminum foil was fixed with tungsten wire and thermal polymerization was conducted in this semi-closed system. The melamine was heated to 550 °C at a heating rate of 1 °C min−1 and then held at 550 °C for 5 h. The sample was then cooled to room temperature at 2 °C min−1.

PHI was synthesized in a quartz tube as described in the literature19. Melon (0.3 g) and KSCN (0.15 g, purity: 98.0% Wako Pure Chem., Ind., Ltd., 164-04555) were mixed and placed in a combustion boat (NIKKATO CORPORATION). The boat was placed at the bottom of a quartz tube and the tube was capped with aluminum foil, as described above. The boat was rapidly heated to 400 °C at a heating rate of 30 °C min−1 and then held at 400 °C for 1 h. After this first heating, the mixture was thermally treated again by heating to 500 °C at a heating rate of 30 °C min−1, held at 500 °C for 30 min, then cooled to room temperature at a cooling rate of 2 °C min−1. The product was washed with acetone and water and separated by centrifugation. Finally, the obtained sample was dried in a desiccator to obtain PHI as a yellow powder.

As shown in Fig. 1a, PHIG was obtained by mixing PHI (15 mg) and ionic liquid (20 mL). All ionic liquid samples were purchased from Kanto Chemical Co. Inc., and were used without further purification. Ionic liquids with a fluoride anion were used to make PHIG: 1-butyl-3-methylimidazolium tetrafluoroborate ([Bmim]BF4), 1-butyl-3-methylimidazolium hexafluorophosphate ([Bmim]PF6), 1-butyl-4,5-dimethyl-imidazole tetrafluoroborate ([Bmmim]BF4), 1-butyl-3-methylimidazolium Bromide ([Bmim]Br) and 1-ethyl-3-methylimidazolium hexafluorophosphate ([Emim]PF6). PHIGs were successfully obtained using all ionic liquids.

### Analysis methods

All photochromism studies of PHI were performed using a white LED (HAYASHI-REPIC, LA-HDF 100NA) as a visible light source.

UV–Vis measurements (V-650 spectrometer, JASCO) of PHIG were performed on samples placed between two quartz plates to combine transmission and diffuse reflection methods. The time variation of specific wavelengths about the PHIG sample between the glass plates was measured using a spectrometer (BIM-6002A, Brolight) in a homemade dark box. The KBr pellet method was used to record FT-IR spectra of the powder samples. XRD analyses were carried out using a diffractometer (Ultima IV, Rigaku) with a Cu Kα radiation source (λ = 0.15496 nm).

Electric current measurements were performed on PHIG pasted on patterned ITO substrate using a source-measure unit (6487, Kethley) under constant voltage (0.5 V) generated by a DC power source (R6144, Advantest).

XPS measurements were performed on PHIG using a PHI 5000 Versa Probe (Ulvac-Phi) instrument with monochromatic Al Kα ( = 1486.6 eV) radiation as the excitation source. The XPS spectra were analyzed with Voigt functions in the XPSPEAK41 software program (written by Raymund W. M. Kwok). PHIG[blue] was probed using a blue laser (λ = 473 nm, KYOCERA SOC, J010BS).

### Theoretical calculations

Energy band calculations were performed using density functional theory (DFT). Models of PHI[K-0], PHI[K-1], and PHI[K-3] were created using Material Studio software (Dassault Systèmes BIOVIA). The band calculations for PHI[K-0], PHI[K-1], and PHI[K-3] were obtained using GGA/PBE with the double numerical (DND) basis set in DMol3. Optical spectra were simulated using time-dependent DFT (TD-DFT) with ALDA. XRD profiles were calculated using the Powdery Diffraction Pattern package in the Visualization for Electronic and Structural Analysis program (VESTA), and the previously reported structure of K-PHI were used for the calculations19.

## Results and discussion

### Photochromism of poly(heptazine imide)

The XRD spectrum of the synthesized PHI is shown in the upper panel of Fig. 1b, and the lower panel shows the calculated diffraction pattern of the model of PHI proposed by Schlomberg et al.19. The calculated XRD spectrum well explains the experimental spectrum, including the (002), (− 110), and (010) diffractions. The FT-IR spectrum of PHI in Fig. S1 in “Supporting Information S1” shows the ν (CN) vibration of a CN heterocyclic structure such as melon, but also clearly shows ν (C≡N), indicating that PHI has a cyano-group instead of the amino group seen in the melon spectrum. Note that spectra of PHI is also different from Poly(triazine imide) especially 1500–1750 cm−1, caused by difference between heptazine and triazine ring20.

The XRD and FT-IR results are in good agreement with those of previous studies19,21, indicating that PHI was successfully synthesized.

Previous studies showed that PHI changes color in response to light12 but only when it is in a solvent, not as a powder, which has prevented research into applications of this material. Here, we succeeded in removing PHI from the solvent by forming a gel by mixing PHI with an ionic liquid. PHIG also changes color under irradiation with visible light, as in solution. It has been confirmed by UV–Vis measurements that there is no degradation of PHI due to gelation as shown in Fig. S2. Furthermore, because ionic liquids are very viscous and extremely low vapor pressure polar solvents, PHIG is stable even under ultra-high vacuum, allowing experiments in a vacuum, such as photoelectron spectroscopy. Such measurements provided many new insights into the properties of PHI including the charge accumulation and are presented below.

Figure 2 shows the results of UV–Vis measurements of PHIG. PHIG[yellow] is the sample in yellow before white-light irradiation and PHIG[blue] is the sample in blue after white-light irradiation. Comparing PHIG[yellow] and PHIG[blue], irradiation with white light does not affect the spectrum below 470 nm but increases the intensity near 650 nm, indicating that the absorption wavelength range of PHIG is expanded by white-light irradiation. The reason why the change in the absorption spectrum seems to be limited compare to its appearance is that the entire sample did not change color and the light-irradiated area on the surface of PHIG is smaller than the probed area. Furthermore, with a short irradiation time, some yellow areas remain even on the surface of PHIG[blue]. PHIG[blue] shows a reversible change in which the color gradually returns to yellow after turning off the light at room temperature, indicating that it is a T-type photochromic substance with thermal decolorization. A similar color change by PHI was reported by Lau et al.12.

### Role of the electron donor in photochromism of PHI

Previous studies on the photochromism of PHI considered that the supply of electrons from the electron donor to PHI causes new absorption15 in the visible wavelength range, resulting in the color change of PHI under irradiation. However, the experimental results given below cannot be explained by this mechanism. In the upper and middle panels of Fig. 3, PHI was immersed in MeOH and lower panel PHI was immersed in Ionic liquid.

In the upper panel, p-PDA (1,4-diaminobenzene), a typical organic electron donor, was dissolved together with PHI. In the lower panel, PHI alone was immersed in MeOH. Note that neither sample is a gel, allowing direct comparison with previous reports. The color of PHI with p-PDA and MeOH changes to blue upon light irradiation. The results obtained using other electron donors (4-MBA: 4-methylbenzyl alcohol and BA: benzylamine) are shown in Fig. S3a: PHI changes to blue by light irradiation regardless of the electron donor used. The IDEAS model for the color change in PHI assumes that the charge supplied to PHI by an electron donor is triggered by light irradiation15. However, the same color change was observed (lower panel) for PHI without an electron donor. Given that ionic liquid is unlikely to be an electron donor because of its large bandgap22, the results in Fig. 3 indicate that an electron donor is not necessarily required for PHI to change color when exposed to light. The same experiments were performed using other solvents and the results are shown in Fig. S3b. The photochromism of PHI occurs in certain solvents. There was an obvious color change of PHI in MeOH and glycerin, and a slight color change in H2O. A previous study23 reported that adding 4-MBA to PHI in H2O resulted in a color change in PHI, and this color change is due to 4-MBA because PHI immersed in H2O does not undergo a color change. However, this does not prove electron donation from 4-MBA to PHI. Figure S4 shows the electron spin resonance (ESR) results for a MeOH solution of PHI. According to previous studies15,19, when PHI receives an electron from the donor, electron radicals should be generated and a sharp peak should appear at 3350 Gauss in the ESR spectrum, but this was not observed for either sample, as shown in Fig. S4. This indicates that PHI does not have electron radicals even when mixed in solution with 4-MBA. A previous study reported that PHI[blue] has a strong ESR signal, which is different from our results. The synthesis methods that were used to prepare PHI in this work and the previous work were essentially identical. Furthermore, the XRD patterns and FT-IR spectra of the obtained PHI are very similar in this and previous work. However, in the previous study15, an ESR signal appeared even for PHI[yellow]. One possible origin for this discrepancy might be due to a small amount of impurity contained in PHI (due to differences in synthetic strategy and sample handling) that gave rise to ESR signals.

The IDEAS model previously suggested to explain the color change of PHI cannot explain the results of Fig. 3 and Fig. S4 because it assumes electron donation from the electron donor to PHI under light irradiation. We propose a new model that does not assume electron donation, based on the following discussion.

### Photochromism with K desorption

Figure 4 shows the angle-resolved XPS spectra of PHIG measured at the take-off angle θ = 45° (yellow data and lines) and 90° (blue data and lines). The PHIG samples were obtained using [Bmmim]BF4. The upper and bottom panels show the results for PHIG[yellow] and PHIG[blue], respectively. The smaller the θ, the more sensitive the measurement at the sample surface. Table S1 shows the binding energies of K 2p and K/NIL (the ratio of the amount of K to nitrogen contained in the Bmmim cation) in each sample. PHIG[yellow] shows only low intensity K 2p, regardless of the angle, whereas in PHIG[blue], the K 2p intensity was clearly angle dependent and increased at 45°. Given that the signal from the surface becomes stronger as Bmmim cation θ becomes smaller in XPS, the results in Fig. 4 show that there is more K+ on the surface of PHIG[blue], probably because the K contained in PHIG[yellow] was released into the ionic liquid as it changed to PHIG[blue]. Figure S5 shows the XPS results for [Bmmim]BF4, PHIG[yellow], PHIG[blue], and PHIG[blue] 90 min after light irradiation of PHIG[blue]. The intensity of K+ increases from PHIG[yellow] to PHIG[blue], and 90 min after terminating light irradiation, the intensity gradually decreases to its original value. These results suggest the involvement of K+ release in the photochromism of PHI.

Next, we examined the chemical shifts of the N 1 s core levels because the release of K should alter the chemical environment of PHI. Figure 5a shows the N 1 s spectrum of the same samples as in Fig. 4. The labels i, ii, and iii in the figure indicate the contributions from different nitrogens, as illustrated in Fig. 5b: i and ii represent the nitrogen in the Bmmim cation and the one in PHI, respectively. Label iii represents the contribution from the nitrogen in the cation contacting the nitrogen in PHI through cation-π interaction. The results show that i barely shifts upon light irradiation, whereas ii and iii are shifted to 0.1 eV lower binding energy because ii is strongly bound to K if not irradiated with light. However, if K+ is released by light irradiation, ii is no longer affected by K and thus is the result of shifting the N 1 s core level to lower binding energy. Moreover, the nitrogen of iii was also affected by the shift of ii to lower binding energy. However, looking at Fig. S5, there is no significant shift of the K 2p core level because the K+ released from PHI is surrounded by BF4 anions and is immediately electrically neutralized. Note that iii is shifted in the same direction as ii rather than the opposite direction, indicating that no charge transfer occurs from [Bmmim]BF4 to PHI, consistent with the result that no charge transfer occurs between the electron donor and PHI in the photochromism of PHIG, as suggested in Fig. 3. In addition, since the energy gap of the ionic liquid is wide and its lowest unoccupied states are farther away from the top of the valence band of PHI, indeed, there is little possibility of charge transfer24. These results directly confirmed the movement of K+ upon light irradiation, affecting the chemical state of PHI. Thus, the release of K+ caused by light irradiation is involved in the photochromism of PHI.

### Reaction at the color change of PHIG

Figure 6 shows the results of the time evolution of the reflection spectrum Rt of PHIG, where t is the time elapsed since the start of light irradiation. Rt was acquired at λ = 575 nm. The natural logarithm of the ratio Rt/R0 was plotted against t, where Rt represents the reflected intensity at a certain time t and R0 represents the intensity at t = 0 s. As shown in Fig. 2, PHIG[blue] absorbs in the long wavelength region when irradiated by white light, so ln(Rt/R0), which represents the reflection spectrum intensity, decreases during irradiation. ln(Rt/R0) starts to return to the value for PHIG[yellow] when irradiation is stopped, so ln(Rt/R0) starts to increase gradually. The color of PHIG changes slowly when the light is switched on. This exponential shift in the concentration of PHIG[blue] shown in Fig. 6 indicates that PHIG is in chemical equilibrium between PHIG[yellow] and PHIG[blue] in the dark state, that light irradiation triggers the system towards a new equilibrium position, and relaxation to the original equilibrium position occurs when irradiation is terminated. This transfer between two equilibrium states is described as follows:

$$\mathrm{PHIG} \; \left[\mathrm{yellow}\right]\underset{{k}_{b}}{\stackrel{{k}_{a}}{\rightleftarrows }}\mathrm{PHIG} \; \left[\mathrm{blue}\right] \;\; (\text{dark} \; \text{state})$$
(1)
$$\mathrm{PHIG} \; \left[\mathrm{yellow}\right]\underset{{k}_{b}^{^{\prime}}}{\stackrel{{k}_{a}^{^{\prime}}}{\rightleftarrows }}\mathrm{PHIG} \; \left[\mathrm{blue}\right] \; \left(\text{irradiation} \; \text{state}\right)$$
(2)

here, ka, kb, ka′, and kb′ are the rate constants for each reaction. The time evolution of change in the concentration of PHIG[blue] during relaxation from the dark state to the irradiated state is expressed by the following formula:

$$-\frac{{R}_{t}}{{R}_{0}}=\frac{{\left[\mathrm{PHIG} \; \left[\mathrm{blue}\right]\right]}_{t}}{{\left[\mathrm{PHIG} \; \left[\mathrm{blue}\right]\right]}_{0}}=\left(1-X\right){e}^{-{k}^{\mathrm{^{\prime}}}t}+X$$
(3)

where k′ means ka′ + kb′, and X is the ratio of [PHIG[blue]] at t = ∞ s to [PHIG[blue]]0 at t = 0 s: [PHIG[blue]] = X [PHIG[blue]]0. Given that the increase in [PHIG[blue]]t/[PHIG[blue]]0 represents an increase in the absorption of PHIG[blue], the reflection spectral intensity is equal to (− RtR0). For each ionic liquid, k in the dark state is smaller than k′ in the irradiated state because in the dark state, the recovery of PHIG[yellow] → PHIG[blue] occurs relatively slowly, so kb becomes smaller and the value of k is also smaller.

In addition, Fig. 6 shows that the slope of ln(Rt/R0) changes for each ionic liquid. Interpreting these results requires consideration of the differences in the viscosity η of ionic liquids. The relationship between the viscosity of each ionic liquid is studied here [Bmim]PF6 > [Emim]PF6 > [Bmim]BF425. Figure 6 shows that the slope of ln(Rt/R0) decreases as η increases, indicating that k 1/η. The relationship between η and ionic diffusivity D in ionic liquids was reported by Noda et al. to be understood according to the Stokes–Einstein form, D 1/η26. In other words, the relation kD 1/η shows that the rate of change of PHIG, k, is directly correlated with the ion diffusion coefficient, D, through the viscosity of the ionic liquid used to form PHIG.

The results of Fig. 6 thus indicate that the change in PHIG is mediated by ion diffusion through the ionic liquid, consistent with the result that K+ ions are involved in this change, as discussed in Fig. 4. The dynamics of the color change in PHIG can thus be interpreted as follows. First, PHIG is in equilibrium between PHIG[yellow] and PHIG[blue], and this reaction is caused by the adsorption and desorption of K+ ions. During the change from PHIG[yellow] to PHIG[blue], K+ ions desorb from PHI, and in the reverse reaction, K+ ions adsorb onto PHI. Furthermore, as PHIG shifts to a new equilibrium state upon light irradiation, the ratio of PHIG[blue] to PHIG[yellow] changes and the ratio of PHIG[blue] becomes larger, so the color of PHIG appears blue. The higher the viscosity of PHIG, the more difficult it is for ions to diffuse, and thus K+ ions are less likely to desorb from PHI and take longer to recombine with PHI, resulting in the rate of change of PHIG being dependent on the viscosity. In the next section, how K adsorption/desorption affects the electronic structure of PHI will be discussed from a theoretical perspective to examine the mechanism underlying photochromism of PHI proposed above.

### Mechanism of the photochromism of PHI

The above discussion suggests that K adsorption and desorption are involved in PHIG photochromism. This was investigated by TD-DFT. Figure 7a shows the results of the calculation of optical absorption for PHI[K-n] (n = 0, 1, and 3) using TD-DFT to be compared with the experimental UV–vis spectra of PHIG[yellow] and PHIG[blue] in Fig. 7b. A crystalline structure of PHI reported by Schlomberg et al. was used19 and the model structures for the calculation are shown in Fig. 7c,d.

The number of K–N bonds in one heptazine imide ring was denoted as n, and the system with n K–N bonds is denoted as PHI[K-n] in the figures. Note that in the following discussion, the quantitative value of the absorption edge is not discussed, but rather the relative spectral shape between the models and the experimental results are compared, in consideration of the effect of underestimation of the band gap calculated using DFT. Although the UV–Vis spectra of all the models shown in Fig. 7a have a large peak around 475 nm, PHI[K-1] and PHI[K-0] have a structure with a shoulder in addition to this band, whereas PHI[K-3] shows no shoulder structure. The shoulder structures observed in the results for PHI[K-1] and PHI[K-0] are also seen in the UV–Vis spectrum of PHI[blue], whereas PHIG[yellow] lacks this structure, as shown in Fig. 7b. This suggests that PHI[K-3] can be attributed as PHIG[yellow]. The spectrum of PHIG[blue] in Fig. 7b shows that the shoulder structure appears due to new absorption around 650 nm. In contrast, PHI[K-0] shows almost no absorption around 650 nm, whereas PHI[K-1] shows large absorption. Therefore, PHIG[blue] is considered to have a structure similar to PHI[K-1].

To support the model discussed above, we examined the chemical shifts of the N 1 s core level observed in the XPS results in Fig. 5a using DFT calculations. The calculated N 1 s core levels of PHI[K-3] and PHI[K-1] are summarized in Table S3. The core level of PHI[K-1] is 0.2 eV lower than the core level of PHI[K-3]. Furthermore, the XPS results show that the core level of PHIG[blue] is shifted to lower binding energy by about 0.1 eV, supporting the desorption of K in the photochromism mechanism of PHI discussed in Fig. 5a, further indicating that the core level of the nitrogen strongly bound to K shifts to lower binding energy upon its desorption.

Based on the above discussion, it is reasonable to assume that PHI[K-1] is PHIG[blue] and PHI[K-3] is PHIG[yellow], which justifies the hypothesis that the band gap decreases with K desorption, causing photochromism, as discussed at Figs. 4 and 5. The interpretation that PHIG[blue] adopts primarily PHI[K-1] states rather than PHI[K-0] states can be understood by considering the entropy contribution to the Gibbs free energy of the system. Figure 8a,b shows the results of energy band calculations for PHIG[K-3] and PHIG[K-1], respectively. Figure 8c,d shows the valence and conduction band orbitals of PHI[K-3] and PHI[K-1] at the Γ point, respectively. Because the calculation of optical absorption shown in Fig. 7a was performed as a direct excitation at the Γ point, we will first discuss the energy gap EΓ at the Γ point. The EΓ of PHIG[K-1] is about 0.2 eV smaller than that of PHIG[K-3] and can be explained as follows. First, the shift of the upper edge of the valence band at the Γ point in PHIG[K-1] compared to PHIG[K-3] is due to the reduced symmetry of the system, increasing the degeneracy of the upper band of the valence states. Second, the lowering of the conduction band edge at the Γ point is attributed to the reduced contribution of nitrogen to the conduction band, as shown in Fig. 8c,d, where the contribution of nitrogen at the center of the heterocyclic ring almost disappears in PHI[K-1] compared to PHI[K-3]. Indeed, the calculated contribution of each element to the conduction band shows that the ratio of nitrogen to carbon is reduced by about 3%. Nitrogen is negatively charged due to its lone pair, lowering the orbital energy. Therefore, the conduction band with a reduced nitrogen contribution shifts to higher binding energy. Figure 8a,b shows that both PHI[K-3] and PHI[K-1] have an indirect gap, Eg, indicating that the probability of charge recombination is low in PHI, i.e., charge separation is high. Indeed, as reported previously11,27, the photoluminescence intensity of PHI is lower than that of melon, which clearly indicates that PHI has high charge separation.

The discussion so far supports that the photochromism in PHIG is caused by K adsorption/desorption, and that the color change is caused by the change in the size of the energy gap as the structure of PHI changes.

### Mechanism of photoconductivity and dark photocatalysis of PHIG

Figure 9 shows the time evolution of the photocurrent in PHIG with a 0.5 V bias. The photocurrent of PHIG shows a characteristic behavior after the light irradiation. PHIG gets in a low electric resistance state under white light irradiation due to the change from PHIG[yellow] to PHIG[blue] and the generation of photo-carriers. Importantly, the amount of charge represented by the areas labeled Q1 and Q2 shown in the figure are different: Q2 is larger than Q1. To clarify this discrepancy between Q1 and Q2, we divided the time variation of the photocurrent into four regions: (1) the region showing a sharp increase in photocurrent immediately after the light is turned on (within about 2 s); (2) the region where photocurrent sharply decreases immediately after (1) and then gradually decays (over about 30 s); (3) the region showing a rapid decrease (within about 1 s) after turning the light off; and (4) the region of slow decay with time (over 60 s after (3)). In (4), the photocurrent shows a long tail which lasts beyond 140 s.

Interpreting the photocurrents in Fig. 9 is aided by the discussion on photocurrents in organic solar cells by McNeil et al.28. First, in (1), a low resistance state occurs because photocarriers are generated in PHI immediately after the start of irradiation with white light. However, after entering region (2), the photocurrent peaks sharply and then immediately declines sharply because the generated photocarriers are trapped in PHI. After the sharp decline, photocarriers are gradually trapped, and the photocurrent slowly decreases. Consequently, the area shown in red mesh indicated by Q1 in Fig. 9 represents the total amount of trapped charge in PHI throughout region (2). In region (3), when irradiation is terminated, the photocarriers in PHI are expelled and the current decreases rapidly. In addition, the trapped carriers in PHI begin to be released in response to the electric field. Then, in region (4), the charge Q1 trapped in (2) is released gradually, and the current slowly decays. In this interpretation, the amount of charge Q1 trapped in (2) should correspond to the area of the red meshed area in (4) Q2, which represents the amount of charge released from the trap. Thus, in general, Q2 is never larger than Q1 and satisfies Q1 ≥ Q2 because there are basically two subsequent behaviors of a trapped charge: either it recombines within the trap, or it is released with a certain probability.

The results of photocurrent measurements for melon gel are shown in Fig. S7. The gel was prepared in the same way as PHIG, using the same ionic liquid and melon, and Q1 > Q2 is satisfied. However, PHIG gives Q1 < Q2, which is inconsistent with the above results. It is usually not possible for the amount of charge released to be greater than the amount of charge trapped. Therefore, we consider this phenomenon to be peculiar to PHIG and propose the “shallow trap charge accumulation” (STCA) model to describe the behavior of carriers in PHIG, as shown in Fig. 10.

Figure 10a shows a conceptual energy diagram that explains the photocurrent shown in Fig. 9. The unusual situation Q1 < Q2 is considered in Fig. 10a. The upper part of Fig. 10a shows the situation where PHIG is irradiated with white light, and the state where optical carriers are generated in the PHIG[yellow] and PHIG[blue] regions. As can be seen from the photographs in Figs. 3 and 9, and as discussed in Fig. 6, not all the areas of PHIG irradiated with white light turn blue and a small number of yellow areas remain. The top and middle panels of Fig. 10c illustrate the changes in PHIG when exposed to light. As discussed in Fig. 6, PHIG is in an equilibrium state between PHIG[yellow] and PHIG[blue], so not all PHIG[yellow] becomes PHIG[blue] when exposed to light. PHIG[blue] has a smaller energy gap than PHIG[yellow], as discussed in Fig. 7, so PHIG[blue] acts as a shallow trap for the whole of PHIG.

Therefore, in (ii) in Fig. 9, some carriers are confined in PHIG[blue], and their total amount corresponds to the trapped charge Q1. When irradiation is stopped, the change from PHIG[blue] to PHIG[yellow] occurs actively, so the areas of PHIG[blue] gradually become smaller. As shown in Fig. 10c, the areas of PHIG[blue] appear as islands embedded in a sea of PHIG[yellow] and they become smaller with time. The resulting change in the appearance of PHIG can be seen in the photographs on the middle and right in Fig. 9. Importantly, the areas of PHIG[blue] that did not previously act as traps become new traps upon isolation from blue areas. In addition, the optical carriers that were supposed to leave from PHIG are trapped in the newly created trap of the PHIG[blue] islands. These newly trapped carriers cause Q1 < Q2, and in typical compounds such as melon, new traps are not generated when light irradiation is stopped, so Q1 ≥ Q2 is satisfied. The shallow traps created by PHIG[blue] islands are different from traps due to defects and impurities in other organic crystals. The charges that are trapped and localized in typical traps immediately recombine within a molecule and thus have a short exciton lifetime, whereas PHI has an indirect energy gap, as described in Fig. 8, and thus the charges trapped in PHIG[blue] islands have a low recombination probability. This low recombination probability appears in the rate of decrease of current observed in region (iv) in Fig. 918. Indeed, as can be seen in the inset of Fig. S7, the rate of decrease in current when light irradiation is stopped is significantly smaller in PHIG than in melon gel. This is due to the low probability of carrier recombination because of the indirect gap in PHI and the short exciton lifetime due to the direct gap in melon, as reported by Akaike et al.1. Also, the carriers originally captured in the trap during irradiation and then released are captured again.

The time evolution of the photocurrent can thus be explained by the STCA model, and this model is also useful for understanding the mechanism of dark photocatalysis by PHI. Figure 10b shows conceptual energy diagrams to explain dark photocatalysis by PHI. Unlike in Fig. 10a, no voltage was applied to PHI and thus it is not necessary to consider the drift motion of the carriers in PHI. In the upper part of Fig. 10b, excitons generated by indirect transition by white-light irradiation are easily separated into electrons and holes. Turning off irradiation results in the state shown at the bottom of Fig. 10b and the charges separated in PHIG[blue] are confined in PHIG[blue] areas through the process described by the STCA model. These accumulated electrons and holes in the PHIG[blue] areas explain the photocatalytic activity of PHI even in the dark (after terminating light irradiation) because some of the accumulated charge undergoes a photocatalytic reaction without deactivation itself in the dark due to the low recombination probability of PHI. These insights provide hints for the development of new photocatalytic materials.

## Conclusion

PHIG, a novel substance obtained by the gelation of PHI with ionic liquids, allowed us to experimentally investigate interesting properties of PHI.

The change in color of PHI by visible light irradiation, and the dark photocatalysis by PHI reported previously, is explained by (1) photochromism and (2) charge accumulation, and they are strongly correlated. Combining XPS and reflection spectroscopy with DFT simulations showed that photochromism is caused by a change in the molecular structure of PHI associated with the adsorption/desorption of K. Interpretation of the time variation of the photocurrent of PHIG resulted in a model named STCA, which was proposed to clarify how charge accumulation occurs: by the capture of charges in regions where the electronic state is modified by light irradiation. In dark photocatalysis, these accumulated charges in PHI are used for the catalysis reaction.

The present findings using photo-stimuli responsive gels, and the mechanism of dark photocatalysis by PHI, provide new guidelines for the future development of new photocatalysts and photo-functional materials.


text:
# Can the decision version of an optimization problem in NP, be in P?

It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore could check whether a a tour exists which costs at most $K$.

Lets assume we are talking about an optimization problem which is either NP or NP-hard. Can the corresponding decision problem ever be in P?

NB: What I am trying to ask is: if a optimization problem cannot be solved in polynomial time, can the corresponding decision problem be solve in polynomial time?

## 1 Answer

Optimization problems cannot belong to NP or be NP-hard any more than apples. NP is a class of decision problems, and NP-hardness is a property of decision problems. When we say that an optimization problem is in NP or is NP-hard, what we really mean is that the corresponding decision problem is in NP or is NP-hard.

• You're right about optimization problems not being in NP, but NP-hard does not only contain decision problems but also optimization problems. Anyway what I want to ask is: if a optimization problem cannot be solved in polynomial time, can the corresponding decision problem be solve in polynomial time? – Héctor van den Boorn Apr 26 '16 at 12:00
• No, actually I'm right about NP-hardness as well. – Yuval Filmus Apr 26 '16 at 12:03
• The more interesting direction is the other one: if the decision version is in P, can we solve the original version in polynomial time? This is the case if, for example, the optimal value is a polynomial-size integer, and the idea is to use binary search (details left to you). – Yuval Filmus Apr 26 '16 at 12:05
• @YuvalFilmus To be fair, NP-hardness is sometimes used in the context of optimization problems, e.g. wikipedia: "It does not restrict the class NP-hard to decision problems, for instance it also includes search problems, or optimization problems." – Tom van der Zanden Apr 26 '16 at 12:07
• @Tom The same is true for NP. For example, when we say that Max Clique is an NP-complete problem, we are implying that the optimization problem Max Clique is in NP. What we really mean is that the decision version of Max Clique is in NP. Therefore, by definition, if an optimization problem is in NP (or NP-hard) then its decision version is in NP (or NP-hard). – Yuval Filmus Apr 26 '16 at 12:11


text:
# non-holomorphic index-raising operator for Jacobi-Maass forms?

Is there a well-defined non-holomorphic index-raising operator $V_l$, taking index-$m$ Jacobi-Maass forms to index-$ml$ Jacobi-Maass forms (same weight), analogous to the holomorphic operator defined in Eichler-Zagier, p.41? I haven't found it in the literature yet.

-