text:
Detector-device-independent quantum key distribution

# Detector-device-independent quantum key distribution

## Abstract

Recently, a quantum key distribution (QKD) scheme based on entanglement swapping, called measurement-device-independent QKD (mdiQKD), was proposed to bypass all detector side-channel attacks. While mdiQKD is conceptually elegant and offers a supreme level of security, the experimental complexity is challenging for practical systems. For instance, it requires interference between two widely separated independent single-photon sources, and the rates are dependent on detecting two photons - one from each source. Here we experimentally demonstrate a QKD scheme that removes the need for a two-photon system and instead uses the idea of a two-qubit single-photon (TQSP) to significantly simplify the implementation and improve the efficiency of mdiQKD in several aspects.

Quantum key distribution (QKD) enables the exchange of cryptographic keys between two separated users, Alice and Bob, who are connected by a potentially insecure quantum channel Bennett and Brassard (1984); Gisin et al. (2002); Scarani et al. (2009); Lo et al. (2014). Unlike conventional key distribution schemes, the security of QKD depends only on the principles of quantum physics and can be proven information-theoretically secure. However, despite the potential of QKD, one still has to be prudent about potential side-channel attacks that may lead to security failures. For example, it has been shown that with detector blinding techniques, it is possible to remotely hack the measurement unit of some QKD systems Lydersen et al. (2010). Although it is possible to implement appropriate countermeasures for specific attacks, one may be wary that the adversary, Eve, could devise new detector control strategies, unforeseen by the users.

To prevent all known and yet-to-be-discovered detector side-channel attacks, a measurement-device-independent QKD (mdiQKD) protocol was proposed Lo et al. (2012). In this scheme, Alice and Bob each randomly prepare one of the four Bennett Brassard (BB84) states Bennett and Brassard (1984) and send it to a third party, Charlie, whose role is to introduce entanglement between Alice and Bob via a Bell-state measurement (BSM) Biham et al. (1996); H. Inamori (2008). Obviously, Alice and Bob do not have to trust Charlie since any other non-entangling measurement would necessarily introduce some noise between them. In practice, mdiQKD can be implemented with phase-randomized weak coherent (BB84) states (WCSs), using either time-bin encoded qubits Rubenok et al. (2013); Liu et al. (2013) or polarization-encoded qubits Ferreira da Silva et al. (2013); Tang et al. (2014). To meet the assumption that Alice and Bob send single photons, as required by mdiQKD, they randomly vary the intensity of their laser pulses and use the decoy-state method Hwang (2003); Lo et al. (2005); Wang (2005) to estimate the fraction of single-photon states sent to and detected by Charlie.

Unfortunately, mdiQKD possesses many drawbacks. Firstly, the achievable secure key rates (SKR) are significantly lower compared to conventional prepare and measure (P&M) QKD systems Dixon et al. (2010); Tanaka et al. (2012); Walenta et al. (2014); Korzh et al. (2014a). This is mainly because a two-photon BSM relies on coincidence detections, meaning that the SKR scales with , where is the single photon detector (SPD) efficiency and is the probability of the source emitting a single-photon 1. Another factor is that a two-photon BSM implemented with linear optics is at most 50% efficient Vaidman and Yoran (1999); Lütkenhaus et al. (1999); Valivarthi et al. (2014) and, when using WCSs, the results from one of the bases cannot be used for the raw-key generation due to an inherent 25% error rate Rubenok et al. (2013); Ferreira da Silva et al. (2013). Furthermore, the resource overhead in the finite-key scenario Curty et al. (2014) is significantly larger compared to common P&M schemes Lim et al. (2014); Korzh et al. (2014a), due to the need to apply the decoy-state method twice (once for each source), increasing the statistical fluctuations. For example, at 150 km, Alice and Bob would have to send at least laser pulses to Charlie before key distillation is possible Curty et al. (2014). Finally, the technological complexity of mdiQKD is greater due to the use of two-photon interference, requiring both photons to be indistinguishable in all degrees of freedom (DOFs): temporal, polarization and frequency.

Here we report on the implementation of a QKD scheme that overcomes the aforementioned limitations but is still secure against all detector side-channel attacks. This bridges the gap between the superior performance and practicality of P&M QKD schemes and the enhanced security offered by mdiQKD. Note that a similar scheme, following the same basic idea, has been proposed elsewhere Gonzalez et al. (2014). Our scheme, henceforth referred to as detector-device-independent QKD (ddiQKD), essentially follows the idea of mdiQKD, however, instead of encoding separate qubits into two independent photons, we exploit the concept of a two-qubit single-photon (TQSP). This scheme has the following advantages: (1) it requires only single-photon interference, (2) the linear-optical BSM is 100% efficient Boschi et al. (1998), (3) the secret key rate scales linearly with the SPD detection efficiency and (4) it is expected that in the finite-key scenario the minimum classical post-processing size is similar to that of P&M QKD schemes. In the following we outline the main concepts and demostrate a proof-of-principle experiment.

The protocol works as follows; see Fig. 1. Alice first prepares a single photon in the qubit state chosen at random from the following set of BB84 states:

 |ψA⟩p∈r⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩|+⟩i=1√2(|H⟩+|V⟩),|−⟩i=1√2(|H⟩−|V⟩),|+i⟩=1√2(|H⟩+i|V⟩),|−i⟩=1√2(|H⟩−i|V⟩),

where the subscript indicates this is a qubit in the polarization DOF of the photon. Alice sends to Bob via an untrusted quantum channel. Upon reception of the photon, Bob encodes his random qubit state in the spatial DOF (hence the subscript “”). To achieve this, Bob sends the photon to a 50/50 beam splitter (BS). We denote and the states of the basis defined by the “upper” and “lower”arms after the BS, respectively. He then applies a phase chosen at random in the set on the lower arm to prepare the state , yielding BB84 states in the spatial modes. Both DOFs have so far been created and manipulated independently of each other, and thus the two-qubit state can be written as .

We then define the following Bell states:

 |Φ±⟩ = 1√2(|H⟩p|u⟩s±|V⟩p|ℓ⟩s), (1) |Ψ±⟩ = 1√2(|H⟩p|ℓ⟩s±|V⟩p|u⟩s). (2)

A complete and deterministic BSM of these states is realized by first applying the unitary transformation and on the upper arm using a half-wave plate (HWP), followed by recombination of the arms on a 50/50 BS, and finally by a projection in the basis using two PBSs on the two output arms followed by four SPDs. In this way, a click on each SPD corresponds to a projection on one of the four Bell states; see Fig. 1.

To show how the raw key establishment functions, let us first define the mutually unbiased bases and . The bit to be established is encoded in Alice’s state, i.e.  and encode bit 0, and and encode bit 1. After the measurement phase, Bob uses an authenticated channel to announce the success of the BSM and reveals the basis he used to encode his qubit. Subsequently, Alice announces whether Bob’s basis choice was compatible with hers. Bob can then determine Alice’s bit value according to Table 1, which shows all of the possible combinations. For example, if , the bit is 0 if he detected or , and 1 otherwise. If more than one detector clicked, Bob announces a successful BSM and assigns a random bit value. Importantly, the knowledge of the bases used by Alice and Bob, along with which of the Bell states Bob obtained, does not reveal Alice’s bit. Hence, Eve does not gain information on the key by controlling Bob’s detectors.

From a security point of view, it is important to consider carefully the operation of Bob’s device. Strictly speaking, the mathematical description of his qubit, outlined previously, holds only if the light state entering the first BS is a single-photon excitation of a single optical-temporal mode. As with any other QKD scheme, it is not possible to guarantee this. Indeed, Eve may send multi-photon states through the quantum channel and break the qubit description. However, such an attack is only detrimental if she can interact with Bob’s prepared states, for instance, by making unambiguous state discrimination measurements on them Scarani et al. (2004). This is not possible since the adversary can only interact with Alice’s qubits. Additionally, if the input is a multi-photon state, with very high probability, more than one detector clicks, in which case Bob would pick a random bit value, increasing the errors in the raw bit string. This is due to the fact that the optical linear circuit of the BSM randomizes the encoded state.

The security of our scheme requires that the final light state (just before the SPDs), taken over all possible encoding choices, is independent of the input light state. In particular, for any input state with a given -photon excitation, the average final state after passing through the linear optical circuit is a fixed state. This requirement is in fact similar to the one used in the security analysis of BB84, where the average of the BB84 states has to be independent of the basis choice Gottesman et al. (2004). Once this requirement is met, the security of the scheme can be obtained following proof techniques for the BB84 QKD scheme. A common method to prove the security of P&M QKD schemes is to consider an equivalent entanglement-based version, where Alice and Bob make random measurements on bipartite quantum states distributed by the adversary. To this end, we point to a formalism that allows us to see Bob’s linear optical circuit as random measurements made on some entangled bipartite state.

First, let us relate the two different DOFs, i.e. , denoting the polarization states of Alice and Bob respectively, while denotes Bob’s spatial state. Since Alice is able to prepare the four polarization BB84 states correctly, it is equivalent to consider the entanglement based version, where Alice first prepares a two-qubit maximally entangled state, , and then performs a projective measurement on one half of the state to prepare the other half for Bob. Mathematically, we have, , where is the positive-operator valued measure (POVM) element corresponding to preparation and is an auxiliary state related to the spatial DOF.

Second, Alice sends the quantum systems and using a single photon through the quantum channel to Bob. At this point, the resulting state is not necessarily a single photon state; it may be a multi-photon state. In this case, the state, after tracing out system , is described by a bipartite density operator, , whose dimension is unknown but fixed, i.e. it could be any -photon light state. Note that we changed the subscript to to reflect the action of the quantum channel. To proceed, we use a result from Ref. (Beaudry et al., 2013, Lemma. 1), which says that if, for any input state, the linear optical circuit (parameterized by ) outputs a state that is fixed on the average, then the encoding can be seen as a purified measurement acting on the same input state and one half of a bipartite pure state, where the other half of the bipartite is the same output state. More formally, let the linear optical circuit be described by a set of completely positive trace-preserving maps, , taking the input quantum system to an output quantum system , such that for any input quantum state , the output quantum state is fixed over all possible encoding choices, i.e. for any . Then, the linear optical circuit is equivalent to making a joint measurement on the same input state, , and one half of a bipartite pure state, , living in a joint quantum system , where the other half gives the fixed state . Therefore, the purification provides a method to analyze the security of our scheme in an entanglement-based picture, where Alice makes random BB84 measurements on one half of a bipartite quantum state, and Bob makes random purified measurements on the other half.

Finally, the security of ddiQKD follows directly from that of the BB84 QKD scheme, with the additional benefit that detectors are excluded from the security analysis. In particular, the security can be obtained by using the entropic uncertainty relation proof technique Tomamichel et al. (2012); Lim et al. (2014): in the asymptotic limit, and under the approximation that the BB84 polarization states are prepared correctly, the secret key fraction is , where is the binary entropy function and is the error rate of the sifted key. In fact, the finite-key security performance of ddiQKD is expected to be similar to the one of the single-photon BB84 Tomamichel et al. (2012) since only single-photon detections are required on Bob’s side. Likewise, for a more practical implementation using the decoy-state method for WCS, we expect the security performance to be similar to the one in Ref. Lim et al. (2014).

We implemented a proof-of-principle experiment as illustrated in Fig. 2. We started with the generation of a pair of correlated photons by type-0 SPDC in a fiber-pigtailed periodically-poled lithium-niobate waveguide (PPLN-WG) Tanzilli et al. (2012). The waveguide was pumped with a continuous wave diode laser (Toptica DL100) at 780 nm and the signal and idler photons were deterministically separated by dense wavelength division multiplexers at 1563.9 nm (200 GHz) and 1556.6 nm (100 GHz), respectively. The idler photon was detected by a free-running InGaAs single-photon detector (ID Quantique ID220). The polarization of the heralded signal photon was set to before passing through a Soleil-Babinet, which allowed us to rotate the state around the equator of the Bloch sphere and prepare Alice’s single-photon state. Bob’s device consisted of a balanced interferometer, with a polarization controller in the upper arm acting as a HWP and a piezo phase modulator in the lower arm. The outputs of the BSM corresponding to and were delayed by 2.5 ns before being combined using two PBSs (see Fig. 2) with the other two outputs, which allowed the use of two detectors for all four outcomes. Bob’s free-running InGaAs SPDs were cooled with a Stirling cooler to and had a dark count rate of less than 50 cps at 25% efficiency Korzh et al. (2014b). The detection events were recorded by a time-to-digital converter (TDC). The of the single photons at Alice was about in a 1 ns coincidence window. Due to the extremely low dark count probability of the InGaAs detectors, the probability of having a double detection at Bob was .

To analyze the detection outcomes for all combinations of Alice and Bob’s settings, we fixed the state prepared by Alice and scanned the phase of Bob’s interferometer. Figure 3 shows four curves, one for each of the polarization states chosen by Alice, representing the normalized probability of each Bell-state being announced at any given phase setting in Bob’s interferometer. The measurement points were fitted in order to calculate the visibility, with the highest average value obtained being for the input state at Bob and the lowest value of for the state. Table 1 shows the theoretical Bell-state announcement probability for every combination of Alice and Bob’s settings. We complete this correlation table with the experimental results by selecting points from Fig. 3 closest to the desired settings for Bob. One can see that the experimental values coincide with the prediction and the overall quantum bit error rate, , was . The total detection rate was around 60 cps.

While the concept of ddiQKD is fundamentally the same as mdiQKD, some subtleties need to be pointed out. For instance, in mdiQKD, Eve can interact with Alice’s and Bob’s qubits, but in our scheme only with Alice’s qubit. Furthermore, we extend the trusted device boundary in Bob’s laboratory to include the linear optical elements of the BSM, leaving only the single-photon detectors as untrusted devices. This means that Eve can have full control over their functionalities, e.g. she can control the response functions of the detectors Liu et al. (2014). But Bob can ensure that no additional information, other than the outcome of the BSM, leaks out of his lab. Indeed, if Eve had access to the output ports of Bob’s PBSs she could carry out a Trojan-horse attack Gisin et al. (2006) in order to gain information about the phase setting of Bob’s interferometer. Note that attacks targeting the state preparation devices are also applicable to mdiQKD, but can be resolved (see Refs. Gonzalez et al. (2014); Xu et al. (2014) for further discussion).

In practice, an implementation of ddiQKD using WCSs together with the decoy-state method could yield SKRs comparable with existing GHz clocked systems Dixon et al. (2010); Tanaka et al. (2012); Walenta et al. (2014); Korzh et al. (2014a). In particular, ultra-fast generation of polarization states could be achieved using a birefringence modulator scheme as used in Ref. Lunghi et al. (2014). We would like to highlight that the concept of TQSP entanglement employed in the ddiQKD scheme can be achieved by using any two DOFs of the single-photon. For example, Alice could encode a time-bin qubit Korzh et al. (2013) followed by Bob’s addition of a polarization qubit to the same photon.

In summary we implemented a ddiQKD protocol that overcomes the main disadvantages of the mdiQKD protocol whilst offering the same level of security. Future theoretical work should focus on deriving a bound on the extractable key length in a finite key scenario. This work paves the way to practical, high-performance and detector-side-channel free QKD.

We would like to acknowledge Gustavo Lima, Guilherme Xavier and Marcos Curty for stimulating discussions regarding the basic idea. We thank ID Quantique and Battelle for the PPLN-WG and the Swiss NCCR QSIT for financial support.

### Footnotes

1. For a WCS , where is the average photon number per pulse. Typical values of are for practical InGaAs SPDs.

### References

1. C. H. Bennett and G. Brassard, in Proc. IEEE Int. Conf. Comp. Sys. Sig. Process. (Bangalore, 1984) pp. 175–179.
2. N. Gisin, G. Ribordy, W. Tittel,  and H. Zbinden, Rev. Mod. Phys. 74, 145 (2002).
3. V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dušek, N. Lütkenhaus,  and M. Peev, Reviews of Modern Physics 81, 1301 (2009).
4. H.-K. Lo, M. Curty,  and K. Tamaki, Nat. Photon. 8, 595 (2014).
5. L. Lydersen, C. Wiechers, C. Wittmann, D. Elser, J. Skaar,  and V. Makarov, Nat. Photonics 4, 686 (2010).
6. H.-K. Lo, M. Curty,  and B. Qi, Phys. Rev. Lett. 108, 130503 (2012).
7. E. Biham, B. Huttner,  and T. Mor, Phys. Rev. A 54, 2651 (1996).
8. H. Inamori, Algorithmica 34, 340 (2008).
9. A. Rubenok, J. A. Slater, P. Chan, I. Lucio-Martinez,  and W. Tittel, Phys. Rev. Lett. 111, 130501 (2013).
10. Y. Liu, T.-Y. Chen, L.-J. Wang, H. Liang, G.-L. Shentu, J. Wang, K. Cui, H.-L. Yin, N.-L. Liu, L. Li, X. Ma, J. S. Pelc, M. M. Fejer, C.-Z. Peng, Q. Zhang,  and J.-W. Pan, Phys. Rev. Lett. 111, 130502 (2013).
11. T. Ferreira da Silva, D. Vitoreti, G. B. Xavier, G. C. do Amaral, G. P. Temporão,  and J. P. von der Weid, Phys. Rev. A 88, 052303 (2013).
12. Z. Tang, Z. Liao, F. Xu, B. Qi, L. Qian,  and H.-K. Lo, Phys. Rev. Lett. 112, 190503 (2014).
13. W.-Y. Hwang, Phys. Rev. Lett. 91, 57901 (2003).
14. H.-K. Lo, X. Ma,  and K. Chen, Phys. Rev. Lett. 94, 230504 (2005).
15. X.-B. Wang, Phys. Rev. Lett. 94, 230503 (2005).
16. A. R. Dixon, Z. L. Yuan, J. F. Dynes, A. W. Sharpe,  and A. J. Shields, Appl. Phys. Lett. 96, 161102 (2010).
17. A. Tanaka, M. Fujiwara, K.-i. Yoshino, S. Takahashi, Y. Nambu, A. Tomita, S. Miki, T. Yamashita, Z. Wang, M. Sasaki,  and A. Tajima, IEEE J. Quantum Electron. 48, 542 (2012).
18. N. Walenta, A. Burg, D. Caselunghe, J. Constantin, N. Gisin, O. Guinnard, R. Houlmann, P. Junod, B. Korzh, N. Kulesza, M. Legré, C. C. W. Lim, T. Lunghi, L. Monat, C. Portmann, M. Soucarros, R. T. Thew, P. Trinkler, G. Trolliet, F. Vannel,  and H. Zbinden, New J. Phys. 16, 013047 (2014)1309.2583 .
19. B. Korzh, C. C. W. Lim, R. Houlmann, N. Gisin, M. J. Li, D. Nolan, B. Sanguinetti, R. Thew,  and H. Zbinden,  (2014a)arXiv:1407.7427 .
20. For a WCS , where is the average photon number per pulse. Typical values of are for practical InGaAs SPDs.
21. L. Vaidman and N. Yoran, Phys. Rev. A 59, 116 (1999).
22. N. Lütkenhaus, J. Calsamiglia,  and K.-A. Suominen, Phys. Rev. A 59, 3295 (1999).
23. R. Valivarthi, I. Lucio-Martinez, A. Rubenok, P. Chan, F. Marsili, V. B. Verma, M. D. Shaw, J. A. Stern, J. A. Slater, D. Oblak, S. W. Nam,  and W. Tittel, Opt. Express 22, 24497 (2014).
24. M. Curty, F. Xu, W. Cui, C. C. W. Lim, K. Tamaki,  and H.-K. Lo, Nat. Commun. 5 (2014).
25. C. C. W. Lim, M. Curty, N. Walenta, F. Xu,  and H. Zbinden, Phys. Rev. A 89, 022307 (2014).
26. P. Gonzalez, L. Rebon, T. F. da Silva, M. Figueroa, C. Saavedra, M. Curty, G. Lima, G. B. Xavier,  and W. A. T. Nogueira,  (2014)arXiv:1410.1422 .
27. D. Boschi, S. Branca, F. De Martini, L. Hardy,  and S. Popescu, Phys. Rev. Lett. 80, 1121 (1998).
28. V. Scarani, A. Acín, G. Ribordy,  and N. Gisin, Phys. Rev. Lett. 92, 057901 (2004).
29. D. Gottesman, H.-K. Lo, N. Lutkenhaus,  and J. Preskill, Quant. Inf. Comput. 5, 325 (2004).
30. N. J. Beaudry, M. Lucamarini, S. Mancini,  and R. Renner, Phys. Rev. A 88, 62302 (2013).
31. M. Tomamichel, C. C. W. Lim, N. Gisin,  and R. Renner, Nat. Commun. 3, 634 (2012).
32. S. Tanzilli, A. Martin, F. Kaiser, M. De Micheli, O. Alibart,  and D. Ostrowsky, Las. Photon. Rev. 6, 115 (2012).
33. B. Korzh, N. Walenta, T. Lunghi, N. Gisin,  and H. Zbinden, Appl. Phys. Lett. 104, 081108 (2014b).
34. Q. Liu, A. Lamas-Linares, C. Kurtsiefer, J. Skaar, V. Makarov,  and I. Gerhardt, Rev. Sci. Instrum. 85 (2014).
35. N. Gisin, S. Fasel, B. Kraus, H. Zbinden,  and G. Ribordy, Phys. Rev. A 73, 22320 (2006).
36. F. Xu, M. Curty, B. Qi,  and H.-K. Lo,  (2014)arXiv:1409.5157 .
37. T. Lunghi, J. B. Brask, C. C. W. Lim, Q. Lavigne, J. Bowles, A. Martin, H. Zbinden,  and N. Brunner,  (2014)arXiv:1410.2790 .
38. B. Korzh, N. Walenta, R. Houlmann,  and H. Zbinden, Opt. Express 21, 19579 (2013).
You are adding the first comment!
How to quickly get a good reply:
• Give credit where it’s due by listing out the positive aspects of a paper before getting into which changes should be made.
• Be specific in your critique, and provide supporting evidence with appropriate references to substantiate general statements.
• Your comment should inspire ideas to flow and help the author improves the paper.

The better we are at sharing our knowledge with each other, the faster we move forward.
The feedback must be of minumum 40 characters


text:
The first use of plus operator in an online search engine

Remember an old plus operator obsoleted by Google in 2011? In many search engines, including Google before October 2011, this operator is used to indicate a mandatory (or an important) keyword. Do you know when was the plus operator first used in an online search engine? I bet few would guess that it happened half a century ago, in the pre-Internet era:

In 1965, TEXTIR permitted users to do some search term weighting. By preceding a term with a plus sign, a searcher could direct TEXTIR to increase the score assigned of that word, and thus raise the score of the source document that contained that word.

How was the online search possible before Internet? One could use a phone line (and apparently a dial-up modem):

Queries were sent to SDC's Q-32 computer in Santa Monica via telephone from a Teletype Model 35 terminal ... In response, the system ... transmitted the texts of retrieved reports back by Teletype in relevance rank order.

Source: A History of Online Information Services 1963-1976 by C. P. Bourne and T.B. Hahn.

The online search service, one of the first of the kind, was developed and provided by the System Development Corporation (SDC). SDC is considered to be the first software company in the world.

It is not the ideas that are overrated, it is the implementation that is undervalued

I think that we, as a society, have come to an important realization: The notion of the Idea Person, who effortlessly produces a stream of ingenious ideas to be implemented by less intelligent underlings, needs to be deflated. At least, many of us do understand that good ideas are not born easily. In contrast, a good idea is a result of a tedious selection process that involves experimentation, reading, backtracking, hard work, and exchange of knowledge. It is also not unusual that the idea evolves substantially in the course of implementation. Yet, little or no credit goes to an Implementation Person.

As a result of the existing imbalance, some people have come to another extreme conclusion: Ideas are not valuable. Here, I have to disagree. Not all ideas are worthless. The problem is that it is hard to distinguish between a good and a bad idea until an implementation is attempted. Nevertheless, a good idea is an important ingredient of progress: Success is not possible without proper implementation, but it is not possible without good ideas either. As it was put by my co-author Anna, it is not the ideas that are overrated, it is the implementation that is undervalued.

Efficient grapecounting in your vineyard via passive computer vision

Believe it or not, the USA is the largest consumer of wine that guzzles more than 10% of all wine produced on the planet. However, it lags somewhat in production. Turns out that maximizing grape yield relies heavily on measurements during the growing season, in particular, on crop estimation. If certain areas are underperforming, it is often possible to fix the issue by, e.g., additional irrigation and fertilization.

Crop estimation is an expensive labor-intensive process that was previously carried out only by humans. The Robotics Institute of Carnegie Mellon University (in collaboration with Cornell University and stakeholders) works on developing automated measuring techniques. At Carnegie Mellon University, the group is lead by Stephen Nuske.

What is truly astonishing is that the proposed technology relies only on passive vision techniques, which are considered unreliable to be used outside a lab. Unlike self-driving cars requiring expensive laser-powered sensing devices called LIDARs, the proposed technology uses only a camera. The camera resides on a small cart that drives at a speed of about 5mph (if I remember correctly, there is also a flash to neutralize variability in lighting). While driving, the camera makes overlapping pictures of grape vines. Obtained images are processed to detect individual grapes and count them!

Although image recognition algorithms have reached a certain level of maturity, it is still challenging to detect individual grapes, because there are millions of potential locations to check in a single picture. This is especially hard when grapes did not ripen (and consequently both leaves and grapes are green). However, the researchers from the Robotics Institute of Carnegie Mellon University can count grapes even in real time! To accomplish this complex task, they use a combination of a quick high-recall low-precision filtering algorithm and a more accurate algorithm that removes false matches. The high-recall low-precision algorithm is an ensemble of two relatively simple key-point detection algorithms. The approach is described in a series of publications. The overall accuracy seems to be pretty good and the technology might be commercialized in not-so-distant future.

To conclude, I would like to note that, in addition to grape counting in your vineyard, Stephen Nuske worked on several other cool projects, where passive vision was applied to real-world problems. These may be interesting to both practitioners and lab scientists specializing in computer vision.

Algorithms to merge sorted lists or arrays

I have written a rather thorough description of algorithms that one can use to merge sorted lists or arrays of integers. Feel free to vote for this description on Quora. Here I decided to duplicate my answer (slightly revised and improved).

The choice of the merging algorithm depends on (1) the distribution of data (2) the hardware that you use. In that, there are several major approaches or a combination thereof that can be used:

1. Classic k-way intersection with the priority queue. I believe it's described in Knuth. All the lists should be sorted in advance. You read the smallest values from each list and put them into the queue. More specifically, you put the pair (value, list id). Then you extract the smallest value using the queue and output it. If it came from list K, you extract the smallest value from the list K and push the smallest pair (value, K) to the priority queue (while simultaneously removing it from list K) . And so on so forth.

Priority queue is not especially fast, in particular, because working with a queue entails a lot of branching (can be slow on both CPUs and GPUs due to branch misprediction). Therefore, other approaches may be more efficient sometimes.

2. Pairwise merge sort. It is a well-known algorithm, so I won't describe it here. However, if you merge two lists, where one is much shorter than other methods can do better.

In particular, you can iterate through a shorter list and find an insertion point in the large list using an exponential search (a fancier and more efficient version of the binary search). We used this approach in the context of list intersection, but the same method works well for unions.

3. Using bitmasks. If your lists are represented as bitmasks, merge is super fast. Extraction of the result can be a bit tricky. However, using modern CPU instructions, you can do it rather easily. Daniel Lemire covered the topic of bitmap decoding extensively. Alternatively, one can use hashing.

Encoding the whole list as a bitmap can be wasteful. This is why, people use some hybrid approaches where only a part of the list is encoded as a bitmap. If you have a sorted list as an input, it can actually may make sense to convert it first to a bitmap and then carry out a union/intersection using the bitmap.

4. Using the ScanCount algorithm. Imagine that the minimum number is zero and the maximum number is M. You can create a table with M+1 elements that are all set to zero initially. To carry out a merge, you have to iterate over lists that you merge. If, during the iteration you encounter the number X, you set the element X in the table to one (or increment it if you need to know the number of lists that contain the number). Finally, you iterate over the (M+1)-element table and check which elements are non-zero. Bonus: input lists do not have to be sorted!

The table may have byte or bit elements. Zeroing table elements before merging can be done in several ways. One very simple approach is via the library function memset (it's memset in C/C++ may have different name in other languages). Though this seems to be naive, memset can zero about 10 billion integers per second for cache-resident data. See the test program here.
ScanCount can be surprisingly efficient.

To fit data into cache, you need to reuse the same small table M ~ 60-100K elements. In practice, of course your numbers will be larger than M. However, you can split your inputs and process each split separately.

5. To conclude, I would mention that there are more advanced so-called adaptive algorithms, which I don't remember off the top of my head. Google something like "adaptive list intersection", or "adaptive list merging".

Branchless code that would leave you speechless (C++ streams are super expensive)

I was looking for a portable C++11 way to check if a file (with a given name) exists. No luck, unfortunately, this functionality will be available only in C++14. However, I found one workaround that left me speechless. It is not actually the solution itself, it is rather a comment that is so fascinating:

Solution:

 bool b = std::ifstream("filename").good();

Comment: Without the branch instructions (like if) it must perform faster as it needs to be called thousands of times.

Gosh! If you care about these kind of micro-optimizations, you should learn about the costs first. A branch misprediction is merely several wasted CPU cycles, but C++ streams are 2 orders of magnitude more costly. Not to mention all the overhead related to the filesystem calls!

Even for a filesystem-less stream, it takes a thousand CPU cycles to construct. Why is it so horribly slow? I have no idea, but such code should be avoided wherever performance is important (of course, we can use it otherwise).

UPDATE: For a good comment on the inefficiency of C++ streams (by Sergey Nepomnyachiy) see my Google+ account.

format: plain


text:
# Solution - Two Particles Perform Linear Simple. Harmonic Motion Along the Same Path of Length 2a and Period T as Shown In the Graph Below. the Phase Difference Between Them is - Differential Equation of Linear S.H.M.

Account
Register

Share

Books Shortlist

#### Question

Two particles perform linear simple. harmonic motion along the same path of length 2A and period T as shown in the graph below. The phase difference between them is..............

(a) zero" "rad

(b) pi/4 rad

(c)pi/2 rad

(d) (3pi)/4 rad

#### Solution

You need to to view the solution
Is there an error in this question or solution?

#### Similar questions VIEW ALL

A particle performing linear S.H.M. has a period of 6*28 seconds and a pathlength of 20 cm. What is the velocity when its displacement is 6 cm from mean position?

view solution

The maximum velocity of a particle performing linear S.H.M. is 0.16 m/s. If its maximum acceleration is 0.64 m/s2, calculate its period.

view solution

Define linear S.H.M.

view solution

#### Video TutorialsVIEW ALL [2]

Solution for question: Two Particles Perform Linear Simple. Harmonic Motion Along the Same Path of Length 2a and Period T as Shown In the Graph Below. the Phase Difference Between Them is concept: Differential Equation of Linear S.H.M.. For the courses 12th HSC Science (Computer Science), 12th HSC Science (Electronics), 12th HSC Science (General)
S


text:
# R Interface to the Keras Deep Learning Library

## Overview

Keras provides a language for building neural networks as connections between general purpose layers. In this vignette we illustrate the basic usage of the R interface to Keras. A self-contained introduction to general neural networks is outside the scope of this document; if you are unfamiliar with the general principles we suggest consulting one of the excellent external tutorials. Suggestions include:

Specific research papers for many advanced layers are also included in the R documentation.

## A Small Example (Boston Housing Data)

Building a model in Keras starts by constructing an empty Sequential model.

library(kerasR)
mod <- Sequential()

The result of Sequential, as with most of the functions provided by kerasR, is a python.builtin.object. This object type, defined from the reticulate package, provides direct access to all of the methods and attributes exposed by the underlying python class. To access these, we use the $ operator followed by the method name. Layers are added by calling the method add. This function takes as an input another python.builtin.object, generally constructed as the output of another kerasR function. For example, to add a dense layer to our model we do the following: mod$add(Dense(units = 50, input_shape = 13))

We have now added a dense layer with 200 neurons. The first layer must include a specification of the input_shape, giving the dimensionality of the input data. Here we set the number of input variables equal to 13. Next in the model, we add an activation defined by a rectified linear unit to the model:

mod$add(Activation("relu")) Now, we add a dense layer with just a single neuron to serve as the output layer: mod$add(Dense(units = 1))

Once the model is fully defined, we have to compile it before fitting its parameters or using it for prediction. Compiling a model can be done with the method compile, but some optional arguments to it can cause trouble when converting from R types so we provide a custom wrapper keras_compile. At a minimum we need to specify the loss function and the optimizer. The loss can be specified with just a string, but we will pass the output of another kerasR function as the optimizer. Here we use the RMSprop optimizer as it generally gives fairly good performance:

keras_compile(mod,  loss = 'mse', optimizer = RMSprop())

Now we are able to fit the weights in the model from some training data, but we do not yet have any data from which to train! Let’s load some using the wrapper function load_boston_housing. We provide several data loading functions as part of the package, and all return data in the same format. In this case it will be helpful to scale the data matrices:

boston <- load_boston_housing()
X_train <- scale(boston$X_train) Y_train <- boston$Y_train
X_test <- scale(boston$X_test) Y_test <- boston$Y_test

Now, we call the wrapper keras_fit in order to fit the model from this data. As with the compilation, there is a direct method for doing this but you will likely run into data type conversion problems calling it directly. Instead, we see how easy it is to use the wrapper function (if you run this yourself, you will see that Keras provides very good verbose output for tracking the fitting of models):

keras_fit(mod, X_train, Y_train,
batch_size = 32, epochs = 200,
verbose = 1, validation_split = 0.1)
output

Notice that the model does not do particularly well here, probably due to over-fitting on such as small set.

pred <- keras_predict(mod, normalize(X_test))
sd(as.numeric(pred) - Y_test) / sd(Y_test)
## [1] 0.7692395

## A Larger Example (MNIST)

To show the power of neural networks we need a larger dataset to make use of. A popular first dataset for applying neural networks is the MNIST Handwriting dataset, consisting of small black and white scans of handwritten numeric digits (0-9). The task is to build a classifier that correctly identifies the numeric value from the scan. We may load this dataset in with the following:

mnist <- load_mnist()
X_train <- mnist$X_train Y_train <- mnist$Y_train
X_test <- mnist$X_test Y_test <- mnist$Y_test
dim(X_train)
## [1] 60000    28    28

Notice that the training data shape is three dimensional (in the language of Keras this is a tensor). The first dimension is the specific sample number, the second is the row of the scan, and the third is the column of the scan. We will use this additional spatial information in the next section, but for now let us flatten the data so that is is just a 2D-Tensor. The values are pixel intensities between 0 and 255, so we will also normalize the values to be between 0 and 1:

X_train <- array(X_train, dim = c(dim(X_train)[1], prod(dim(X_train)[-1]))) / 255
X_test <- array(X_test, dim = c(dim(X_test)[1], prod(dim(X_test)[-1]))) / 255

Finally, we want to process the response vector y into a different format as well. By default it is encoded in a one-column matrix with each row giving the number represented by the hand written image. We instead would like this to be converted into a 10-column binary matrix, with exactly one 1 in each row indicating which digit is represented. This is similar to the factor contrasts matrix one would construct when using factors in a linear model. In the neural network literature it is call the one-hot representation. We construct it here via the wrapper function to_categorical. Note that we only want to convert the training data to this format; the test data should remain in its original one-column shape.

Y_train <- to_categorical(mnist$Y_train, 10) With the data in hand, we are now ready to construct a neural network. We will create three blocks of identical Dense layers, all having 512 nodes, a leaky rectified linear unit, and drop out. These will be followed on the top output layer of 10 nodes and a final softmax activation. These are fairly well-known choices for a simple dense neural network and allow us to show off many of the possibilities within the kerasR interface: mod <- Sequential() mod$add(Dense(units = 512, input_shape = dim(X_train)[2]))
mod$add(LeakyReLU()) mod$add(Dropout(0.25))

mod$add(Dense(units = 512)) mod$add(LeakyReLU())
mod$add(Dropout(0.25)) mod$add(Dense(units = 512))
mod$add(LeakyReLU()) mod$add(Dropout(0.25))

mod$add(Dense(10)) mod$add(Activation("softmax"))

We then compile the model with the “categorical_crossentropy” loss and fit it on the training data:

keras_compile(mod,  loss = 'categorical_crossentropy', optimizer = RMSprop())
keras_fit(mod, X_train, Y_train, batch_size = 32, epochs = 5, verbose = 1,
validation_split = 0.1)

Now that the model is trained, we could use the function keras_predict once again, however this would give us an output matrix with 10 columns. It is not too much work to turn this into predicted classes, but kerasR provides keras_predict_classes that extracts the predicted classes directly. Using this we are able to evaluate the data on the test set.

Y_test_hat <- keras_predict_classes(mod, X_test)
table(Y_test, Y_test_hat)
mean(Y_test == Y_test_hat)
##       Y_test_hat
## Y_test         0    1    2    3    4    5    6    7    8    9
##           0  952    1    5    0    1   11    4    1    3    2
##           1    0 1121    5    0    0    1    2    0    6    0
##           2    1    4  987    0   16    0    3    9   12    0
##           3    0    1   17  946    3   13    0   15    6    9
##           4    0    0    3    0  965    0    1    1    1   11
##           5    2    1    2   17    8  812    9    2   27   12
##           6    4    3    2    0   13    7  923    0    6    0
##           7    1    7    8    1    4    1    0  999    0    7
##           8    2    1    6    7    5    4    0    8  937    4
##           9    1    7    1    5   18    3    1   13    2  958
## [1] 0.96

Looking at the mis-classification rate and the confusion matrix, we see that the neural network performs very well (with a classification rate around 95%). It’s possible to get slightly higher with strictly dense layers by employing additional tricks and using larger models with more regularization. To increase the model drastically requires the use of convolutional neural networks (CNN), which we will look at in the next section.

## Convolutional neural networks

To begin, we load the MNIST dataset in once again, but this time increase the number of dimension in the X_train tensor by one rather than reducing it by one. These images are black and white and one way to think about this additional dimension is that it represents a “gray” channel.

mnist <- load_mnist()

X_train <- array(mnist$X_train, dim = c(dim(mnist$X_train), 1)) / 255
Y_train <- to_categorical(mnist$Y_train, 10) X_test <- array(mnist$X_test, dim = c(dim(mnist$X_test), 1)) / 255 Y_test <- mnist$Y_test

Now we build a CNN model by using the convolution specific Conv2D and MaxPooling layers. The flatten layer converts its inputs into a 2-dimensional tensor so that we can follow up with Dense layers on the top. Using deep convolution layers followed by Dense layers at the top of the network are a common design pattern in neural networks.

mod <- Sequential()

mod$add(Conv2D(filters = 32, kernel_size = c(3, 3), input_shape = c(28, 28, 1))) mod$add(Activation("relu"))
mod$add(Conv2D(filters = 32, kernel_size = c(3, 3), input_shape = c(28, 28, 1))) mod$add(Activation("relu"))
mod$add(MaxPooling2D(pool_size=c(2, 2))) mod$add(Dropout(0.25))

mod$add(Flatten()) mod$add(Dense(128))
mod$add(Activation("relu")) mod$add(Dropout(0.25))
mod$add(Dense(10)) mod$add(Activation("softmax"))

Once the model has been created, we compile it and fit it to the data using the exact same functions as previously used.

keras_compile(mod,  loss = 'categorical_crossentropy', optimizer = RMSprop())
keras_fit(mod, X_train, Y_train, batch_size = 32, epochs = 5, verbose = 1,
validation_split = 0.1)

And we see that this new data has improved the overall classification rate:

Y_test_hat <- keras_predict_classes(mod, X_test)
table(Y_test, Y_test_hat)
mean(Y_test == Y_test_hat)
##       Y_test_hat
## Y_test    0    1    2    3    4    5    6    7    8    9
##           0  970    0    0    0    2    0    5    0    1    2
##           1    0 1133    2    0    0    0    0    0    0    0
##           2    2    2 1023    0    2    0    0    3    0    0
##           3    0    0    1 1006    0    1    0    1    1    0
##           4    1    0    0    0  975    0    2    0    1    3
##           5    3    0    0    9    0  874    3    0    1    2
##           6    4    2    0    0    4    4  944    0    0    0
##           7    0    4   10    1    0    0    0 1011    1    1
##           8    4    0    4    3    3    0    0    1  953    6
##           9    1    0    1    1    9    2    0    6    0  989
## 0.9878

We now have a classification rate of over 98.7%, converting almost twice as many mis-classified digits from before into the correct buckets now.

## Recurrent Neural Networks (RNN) with IMDB

As a final example, we will demonstrate the usage of recurrent neural networks in Keras. RNNs are able to “hold their state” in between inputs, and therefore are useful for modeling a sequence of data such as occurs with a time series or with a collection words in a text. Here we will use them to predict whether a movie review from IMDB is generally positive (1) or negative (0). We’ll load the data in using a similar command as with the Boston Housing Data and MNIST, but here the load functions has a few options that we can set. Once the data is loaded, we’ll use the wrapper pad_sequences to make sure every review has exactly 100 words (those with fewer get padded with a special “word” coded as zeros). Because there are only two classes, we can keep Y_train in its default format.

imdb <- load_imdb(num_words = 500, maxlen = 100)

X_train <- pad_sequences(imdb$X_train[1:4000], maxlen = 100) Y_train <- imdb$Y_train[1:4000]
X_test <- pad_sequences(imdb$X_train[4001:5736], maxlen = 100) Y_test <- imdb$Y_train[4001:5736]

Notice that there is not an explicit test set so we made that manually by using only the first 4000 document for training. Now we’ll build a model that includes an Embedding layer. This maps each word index in X_train into a 500 dimensional space. If you are familiar with the word2vec or GloVe algorithms, these are just particular, well-known examples of word embeddings. Following the embedding we will flatten the output and add a Dense layer before predicting the output. As we only have a single output, we’ll use a sigmoid activation rather than a softmax.

mod <- Sequential()

mod$add(Embedding(500, 32, input_length = 100, input_shape = c(100))) mod$add(Dropout(0.25))

mod$add(Flatten()) mod$add(Dense(256))
mod$add(Dropout(0.25)) mod$add(Activation('relu'))

mod$add(Dense(1)) mod$add(Activation('sigmoid'))

We use almost the exact same commands to compile and fit the model, but here modify the loss to be “binary_crossentropy” because we have only one column in the output. We also found that the learning rate needed to be made slightly smaller as to not overfit the data.

keras_compile(mod,  loss = 'binary_crossentropy', optimizer = RMSprop(lr = 0.00025))
keras_fit(mod, X_train, Y_train, batch_size = 32, epochs = 10, verbose = 1,
validation_split = 0.1)

Now we predict the raw values and round to the nearest integer, which should be either 0 or 1, and compare to the actual test set.

Y_test_hat <- keras_predict(mod, X_test)
table(Y_test, round(Y_test_hat))
mean(Y_test == as.numeric(round(Y_test_hat)))
## Y_test   0   1
##     0 609 189
##     1 175 763
## [1] 0.7903226

This gives a classification rate of 79%. We can try to improve that by including a Long-Short Term Memory Unit (LSTM), an explicit RNN layer, in the model. This is easy to program, but it makes the model learn about 5-10 times slower, at least if you are not running on a dedicated GPU.

mod <- Sequential()

mod$add(Embedding(500, 32, input_length = 100, input_shape = c(100))) mod$add(Dropout(0.25))

mod$add(LSTM(32)) mod$add(Dense(256))
mod$add(Dropout(0.25)) mod$add(Activation('relu'))

mod$add(Dense(1)) mod$add(Activation('sigmoid'))

Which we compile and fit as before:

keras_compile(mod,  loss = 'binary_crossentropy', optimizer = RMSprop(lr = 0.00025))
keras_fit(mod, X_train, Y_train, batch_size = 32, epochs = 10, verbose = 1,
validation_split = 0.1)

The test results do offer an improvement:

Y_test_hat <- keras_predict(mod, X_test)
mean(Y_test == as.numeric(round(Y_test_hat)))
## Y_test   0   1
##      0 579 219
##      1  84 854
## [1] 0.8254608

With the classification rate now up to 82.5%. The real power of RNNs, however, really comes out with larger models.

## Saving models

Because most of the objects returned by kerasR functions are references to Python objects, trying to save them with readRDS or other R-specific functions will generally fail. Instead, you should use one of the three specific wrapper included with kerasR. Given the model from the previous fits, we can do any one of the following:

keras_save(mod, "full_model.h5")
keras_save_weights(mod, "weights_model.h5")
keras_model_to_json(mod, "model_architecture.json")

The first saves the entire model, which is more than likely what most users would want, as a binary file. The second saves only the weights as a binary file; the actual model architecture would have to be created again in R. Finally, the last saves just a json description of the model. This is probably most helpful because it gives a human-readable description of your model architecture. The follow functions show how to read these outputs back into R, respectively:

mod <- keras_load("full_model.h5")
mod <- keras_model_to_json("model_architecture.json")

Note that all three outputs can be read directly into a Python session running the keras module.

Another fantastic feature in Keras is the inclusion of several pretrained, state of the art, image processing models. We will show a small example of using InceptionV3 to classify a photo of an elephant. Specifically, let’s classify this elephant photo:

To begin with, let us load the InceptionV3 model into R:

inception <- InceptionV3(weights='imagenet')

And then, we will use the wrapper load_img to load the elephant image into R as a python object, and then convert it into an array with img_to_array and expand_dims:

img <- load_img("elephant.jpg", target_size = c(299, 299))
x <- img_to_array(img)
x <- expand_dims(x, axis = 0)

We specifically ask that the image be converted into a 299 by 299 image, the size of the images used to train VGG19 from imagenet. The photo must then also undergo the exact same preprocessing used on images that trained InceptionV3, which in this case just divides all the pixels by 255

x <- x / 255

We can get the raw prediction categories with

pred <- keras_predict(inception, x)

But even more directly, we can take this output and get category names:

> unlist(decode_predictions(pred, model = "InceptionV3", top = 3))
[1] "n01871265"         "tusker"            "0.546035408973694"
[4] "n02504013"         "Indian_elephant"   "0.247862368822098"
[7] "n02504458"         "African_elephant"  "0.143739387392998"

And we see that VGG19 correctly identifies the most likely animal in the photo as an elephant. More specifically, it spreads the probability weights over 3 specific sub-types of elephant.


text:
# Compute $\int_{0}^{1}\frac{\ln(x) \ln^2 (1-x)}{x} dx$

Compute $$\int_{0}^{1}\frac{\ln(x) \ln^2 (1-x)}{x} dx$$

I'm looking for some nice proofs at this problem. One idea would be to use Taylor expansion and then integrating term by term. What else can we do? Thanks.

• Concerning Euler's early work you may see this article from Sandifer's excellent 'How Euler did it'. – Raymond Manzoni Sep 7 '12 at 8:04
• @Raymond Manzoni: it's a nice paper! – user 1591719 Sep 7 '12 at 8:09
• I'm really glad that such questions exist! If they weren't around then we'd need to invent them. This way one may see the real beauty of calculus (my opinion) :-) – user 1591719 Sep 7 '12 at 8:34

This answer is from my old calculation.

First, assume we are well aware of the following famous result.

$$\zeta(2) =\frac{\pi^{2}}{6}, \quad \zeta(4) =\frac{\pi^{4}}{90}$$

Next, by a simple calculation we obtain

$$H_{n} := \sum_{k=1}^{n} \frac{1}{k} =\int_{0}^{1}\frac{1-t^{n}}{1-t}\, dt.$$

and

$$\frac{\log (1-x)}{1-x}\ =\ -\sum_{n=1}^{\infty}H_{n}x^{n}.$$

Finally, define the polylogarithm as

$$\mathrm{Li}_{s}(x) :=\sum_{n=1}^{\infty} \frac{x^n}{n^s},$$

so that it satisfies the recurrence relation

$$\mathrm{Li}_{1}(x) =-\log (1-x) , \quad \mathrm{Li}_{s+1}(x) =\int_{0}^{x}\frac{\mathrm{Li}_{s}(t)}{t}\, dt$$

and the identity

$$\mathrm{Li}_{s}(1) =\zeta(s).$$

The the all-in-one straight calculation goes as follows:

\begin{align*} \int_{0}^{1}\frac{\log x\log^{2}(1-x)}{x}\, dx & = \int_{0}^{1}\frac{\log (1-x)\log^{2}x}{1-x}\, dx = -\sum_{n=1}^{\infty}H_{n}\int_{0}^{1}x^{n}\log^{2}x\, dx\\ & = -2\sum_{n=1}^{\infty}\frac{H_{n}}{(n+1)^{3}}\\ & = 2\sum_{n=1}^{\infty}\left[\frac{1}{(n+1)^{4}}-\frac{H_{n+1}}{(n+1)^{3}}\right] = 2\sum_{n=0}^{\infty}\left[\frac{1}{(n+1)^{4}}-\frac{H_{n+1}}{(n+1)^{3}}\right]\\ & = 2\zeta(4)-2\sum_{n=1}^{\infty}\frac{H_{n}}{n^{3}}\\ & = 2\zeta(4)-2\sum_{n=1}^{\infty}\frac{1}{n^{3}}\int_{0}^{1}\frac{1-t^{n}}{1-t}\, dt = 2\zeta(4)-2\int_{0}^{1}\frac{\zeta(3)-\mathrm{Li}_{3}(t)}{1-t}\, dt\\ & = 2\zeta(4)+\left[2 (\zeta(3)-\mathrm{Li}_{3}(t))\log (1-t)\right]_{0}^{1}+2\int_{0}^{1}\frac{\mathrm{Li}_{2}(t)\log (1-t)}{t}\, dt\\ & = 2\zeta(4)-2\int_{0}^{1}\mathrm{Li}_{2}(t)\frac{d\mathrm{Li}_{2}(t)}{dt}\, dt\\ & = 2\zeta(4)-\left[\mathrm{Li}_{2}^{2}(t)\right]_{0}^{1} = 2\zeta(4)-\zeta(2)^{2} = \frac{\pi^{4}}{45}-\frac{\pi^{4}}{36} = -\frac{\pi^{4}}{180}\\ & = -\frac{1}{2}\zeta(4). \end{align*}

• An amazing answer! – user 1591719 Sep 7 '12 at 7:49
• it would be so nice to have many answers / different approaching ways for questions like this one. :-) – user 1591719 Sep 7 '12 at 8:01
• I just noticed that also $\int_{0}^{1}\frac{\ln^2(x) \ln (1-x)}{x} dx$ has a nice result that involves $\zeta(4)$. – user 1591719 Sep 10 '12 at 8:06
• @Chris'ssister: you may find many integrals of this kind in my link (around (417)) to your other thread $\sum_{n=1}^{\infty}\dfrac {1\cdot 3\cdots (2n-1)} {2\cdot 4\cdots (2n)\cdot (2n+1)}$ (see too (437) !). – Raymond Manzoni Sep 10 '12 at 8:20
• @Raymond Manzoni: thanks! That is great link. I'm trying to learn tricks about solving very difficult integrals and Euler sums. – user 1591719 Sep 10 '12 at 8:21

The Taylor expansion approach gives you $-2 \sum_{k=1}^\infty H_k/(k+1)^3$ where $H_k = \sum_{n=1}^k 1/n$. Wolfram Alpha says this is $-\pi^4/180$, but I don't know how it gets that.

• adding the $k+1$ term to $H_k$ we get $\ 2\zeta(4)-2\sum_{k=1}^\infty \frac {H_k}{k^4}$. Euler found (24) of mathworld $2\sum_{k=1}^\infty \frac {H_k}{k^m}=(m+2)\zeta(m+1)-\sum_{n=1}^{m-2}\zeta(m-n)\zeta(n+1)$. I didn't verify this... – Raymond Manzoni Sep 7 '12 at 6:55
• @Raymond Manzoni: do you know some free paper with nice proofs for these sums? – user 1591719 Sep 7 '12 at 7:04
• @Chris'ssister: I don't have my references here but free papers about Euler sums (or MZV multiple zeta values) are numerous (Borwein, Bailey, Broadhurst and many physicists). Start perhaps with Wolfram Euler sums (references look fine!). – Raymond Manzoni Sep 7 '12 at 7:08
• @Raymond Manzoni: OK. Thanks. – user 1591719 Sep 7 '12 at 7:13
• @Chris'ssister: many results were obtained in an experimental way (LLL PSLQ) in the early nineties as seen in this paper of Bailey. Compendium of results (click on one of the names for other papers). It's a rather interesting subject ! – Raymond Manzoni Sep 7 '12 at 7:31
• thanks for the references. (+1) – user 1591719 Sep 7 '12 at 7:35

Note that

\begin{align} {\Gamma\pars{\mu + 1} \over \Gamma\pars{1 + \mu - n}} & = {\Gamma\pars{\mu + 1} \over \pi/\braces{\Gamma\pars{n - \mu}\sin\pars{\pi\bracks{n - \mu}}}} = {\pars{-1}^{n + 1} \over \pi}\,\sin\pars{\pi\mu} \Gamma\pars{\mu + 1}\Gamma\pars{n - \mu} \\[5mm] & = \pars{-1}^{n + 1}\,\mu \braces{\Gamma\pars{1}\Gamma\pars{n} + \bracks{\Gamma'\pars{1}\Gamma\pars{n} - \Gamma\pars{1}\Gamma'\pars{n}}\mu} + \,\mrm{O}\pars{\mu^{3}} \\[5mm] & = \pars{-1}^{n + 1}\,\Gamma\pars{n}\mu + \pars{-1}^{n + 1}\bracks{-\gamma\pars{n - 1}! -\pars{n - 1}!\,\Psi\pars{n}}\color{#f00}{\mu^{2}} + \,\mrm{O}\pars{\mu^{3}} \\[5mm] & = \pars{-1}^{n + 1}\,\Gamma\pars{n}\mu - \pars{-1}^{n + 1}\pars{n - 1}!\,H_{n - 1}\,\color{#f00}{\mu^{2}} + \,\mrm{O}\pars{\mu^{3}} \end{align}

such that $\ds{\left.\partiald[2]{}{\mu}{\Gamma\pars{\mu + 1} \over \Gamma\pars{1 + \mu - n}}\right\vert_{\ \mu\ =\ 0^{+}} = -2\pars{-1}^{n + 1}\pars{n - 1}!\,H_{n - 1}}$

Expression \eqref{1} becomes \begin{align} &\int_{0}^{1}{\ln\pars{x}\ln^{2}\pars{1 - x} \over x}\,\dd x = -\sum_{n = 1}^{\infty}{1 \over n!}\, \bracks{-2\pars{-1}^{n + 1}\pars{n - 1}!\,H_{n - 1}}\, {\pars{-1}^{n} \over n^{2}} = -2\sum_{n = 1}^{\infty}{H_{n - 1} \over n^{3}} \\[5mm] & = -2\sum_{n = 1}^{\infty}{H_{n} \over n^{3}} + 2\sum_{n = 1}^{\infty}{1 \over n^{4}} = -2\pars{\pi^{4} \over 72} + 2\zeta\pars{4} = -\,{5 \over 2}\,\zeta\pars{4} + 2\zeta\pars{4} = \bbx{-\,{1 \over 2}\,\zeta\pars{4}} \end{align}

Note that $\ds{\sum_{n = 1}^{\infty}{H_{n} \over n^{3}} = {\pi^{4} \over 72} = {5 \over 4}\,\zeta\pars{4}}$ is a well known identity. See expression $\pars{19}$ in this page.

$\ds{\Huge\left. b\right)}$ \begin{align} &\int_{0}^{1}{\ln\pars{x}\ln^{2}\pars{1 - x} \over x}\,\dd x = {1 \over 3}\int_{0}^{1}\bracks{% \ln^{3}\pars{x \over 1 - x} - \ln^{3}\pars{x}}\,{\dd x \over x} \\[5mm] + &\ {1 \over 3}\int_{0}^{1}{\ln^{3}\pars{1 - x} \over x}\,\dd x\ +\ \underbrace{\int_{0}^{1}{\ln^{2}\pars{x}\ln\pars{1 - x} \over x}\,\dd x} _{\ds{-\int_{0}^{1}\mrm{Li}_{2}'\pars{x}\ln^{2}\pars{x}\,\dd x}}\label{2}\tag{2} \end{align}

Note that

\begin{align} {1 \over 3}\int_{0}^{1}{\ln^{3}\pars{1 - x} \over x}\,\dd x = {1 \over 3}\int_{0}^{1}{\ln^{3}\pars{x} \over 1 - x}\,\dd x = \int_{0}^{1}\ln\pars{1 - x}{\ln^{2}\pars{x} \over x}\,\dd x = -\int_{0}^{1}\mrm{Li}_{2}'\pars{x}\ln^{2}\pars{x}\,\dd x \end{align} such that \eqref{2} is reduced to \begin{align} \int_{0}^{1}{\ln\pars{x}\ln^{2}\pars{1 - x} \over x}\,\dd x & = \underbrace{{1 \over 3}\int_{0}^{1}\bracks{% \ln^{3}\pars{x \over 1 - x} - \ln^{3}\pars{x}}\,{\dd x \over x}} _{\ds{\mc{I}_{1}}} \\[5mm] & -\ \underbrace{2\int_{0}^{1}\mrm{Li}_{2}'\pars{x}\ln^{2}\pars{x}\,\dd x} _{\ds{\mc{I}_{2}}}\ =\ \mc{I}_{1} - \,\mc{I}_{2}\label{3}\tag{3} \end{align}

Hereafter, I'll evaluate $\ds{\,\mc{I}_{1}}$ and $\ds{\,\mc{I}_{2}}$.

$\ds{\large\quad\mc{I}_{1}:\ ?}$. \begin{align} \mc{I}_{1} & \equiv {1 \over 3}\int_{0}^{1}\bracks{% \ln^{3}\pars{x \over 1 - x} - \ln^{3}\pars{x}}\,{\dd x \over x} \\[5mm] & = \lim_{\epsilon \to 0^{+}}\bracks{% {1 \over 3}\int_{\epsilon}^{1}\ln^{3}\pars{x \over 1 - x}\,{\dd x \over x} - {1 \over 3}\int_{\epsilon}^{1}{\ln^{3}\pars{x} \over x}\,\dd x} \end{align} In the RHS first integral, lets make the change $\ds{{x \over 1 - x} \mapsto x}$: \begin{align} \mc{I}_{1} & = \lim_{\epsilon \to 0^{+}}\bracks{% {1 \over 3}\int_{\epsilon/\pars{1 - \epsilon}}^{\infty} {\ln^{3}\pars{x} \over x\pars{1 + x}}\,\dd x - {1 \over 3}\int_{\epsilon}^{1}{\ln^{3}\pars{x} \over x}\,\dd x} \\[5mm] & = \lim_{\epsilon \to 0^{+}}\left[% -\,{1 \over 3}\int_{\epsilon}^{\epsilon/\pars{1 - \epsilon}} {\ln^{3}\pars{x} \over x\pars{1 + x}}\,\dd x + {1 \over 3}\int_{\epsilon}^{\infty}{\ln^{3}\pars{x} \over x\pars{1 + x}} \,\dd x\right. \\[5mm] & \left.\phantom{= \lim_{\epsilon \to 0^{+}}\left[\right]}- {1 \over 3}\int_{\epsilon}^{1}{\ln^{3}\pars{x} \over x}\,\dd x\right] \end{align} The RHS first integral vanishes out when $\ds{\epsilon \to 0^{+}}$: \begin{align} \mc{I}_{1} & = {1 \over 3}\int_{0}^{1}\ln^{3}\pars{x} \bracks{{1 \over x\pars{1 + x}} - {1 \over x}}\,\dd x + {1 \over 3}\int_{1}^{\infty}{\ln^{3}\pars{x} \over x\pars{1 + x}}\,\dd x \\[5mm] & = -\,{1 \over 3}\int_{0}^{1}{\ln^{3}\pars{x} \over 1 + x}\,\dd x + {1 \over 3}\int_{1}^{\infty}{\ln^{3}\pars{x} \over x\pars{1 + x}}\,\dd x \end{align} In the second integral, lets $\ds{x \mapsto 1/x}$: \begin{align} \mc{I}_{1} & = -\,{1 \over 3}\int_{0}^{1}{\ln^{3}\pars{x} \over 1 + x}\,\dd x + {1 \over 3}\int_{1}^{0}{\ln^{3}\pars{1/x} \over \pars{1/x}\pars{1 + 1/x}} \pars{-\,{1 \over x^{2}}}\,\dd x \\[5mm] & = -\,{2 \over 3}\int_{0}^{1}{\ln^{3}\pars{x} \over 1 + x}\,\dd x = {2 \over 3}\int_{0}^{-1}{\ln^{3}\pars{-x} \over 1 - x}\,\dd x = 2\int_{0}^{-1}\ln\pars{1 - x}\,{\ln^{2}\pars{-x} \over x}\,\dd x \\[5mm] & = -2\int_{0}^{-1}\mrm{Li}_{2}'\pars{x}\ln^{2}\pars{-x}\,\dd x = 4\int_{0}^{-1}\mrm{Li}_{3}'\pars{x}\ln\pars{-x}\,\dd x = -4\int_{0}^{-1}\mrm{Li}_{4}'\pars{x}\,\dd x \\[5mm] & = -4\,\underbrace{\mrm{Li}_{4}\pars{-1}}_{\ds{-\,{7 \over 8}\,\zeta\pars{4}}} \implies \bbx{\,\mc{I}_{1} = {7 \over 2}\,\zeta\pars{4}}\label{4}\tag{4} \end{align}
$\ds{\large\quad\mc{I}_{2}:\ ?}$. \begin{align} \mc{I}_{2} & \equiv 2\int_{0}^{1}\mrm{Li}_{2}'\pars{x}\ln^{2}\pars{x}\,\dd x = -4\int_{0}^{1}\mrm{Li}_{3}'\pars{x}\ln\pars{x}\,\dd x = 4\int_{0}^{1}\mrm{Li}_{4}\pars{x}\,\dd x = 4\mrm{Li}_{4}\pars{1} \\[5mm] & \implies \bbx{\,\mc{I}_{2} = 4\zeta\pars{4}}\label{5}\tag{5} \end{align}
With \eqref{3}, \eqref{4} and \eqref{5}: \begin{align} &\int_{0}^{1}{\ln\pars{x}\ln^{2}\pars{1 - x} \over x}\,\dd x = {7 \over 2}\,\zeta\pars{4} - 4\zeta\pars{4} \end{align} $$\bbox[#ffe,15px,border:1px dotted navy]{\ds{% \int_{0}^{1}{\ln\pars{x}\ln^{2}\pars{1 - x} \over x}\,\dd x = -\,{1 \over 2}\,\zeta\pars{4}}}$$

In this answer I will make use of a Maclaurin series expansion for the term $\ln^2 (1 - x)$, which I show here to be $$\ln^2 (1 - x) = 2 \sum_{n = 2}^\infty \frac{H_{n - 1} x^n}{n},$$ and the well-known Euler sum of $$\sum_{n = 1}^\infty \frac{H_n}{n^3} = \frac{1}{2} \zeta^2 (2),$$ several proofs for which can be found here.

From the above Maclaurin series expansion for $\ln^2 (1 - x)$ the integral can be written as \begin{align*} \int_0^1 \frac{\ln (x) \ln^2 (1 - x)}{x} \, dx = 2 \sum_{n = 2}^\infty \int_0^1 x^{n - 1} \ln x \, dx. \end{align*} The integral that appears to the right can be readily found by parts. The result is $$\int_0^1 x^{n - 1} \ln x \, dx = -\frac{1}{n^2}.$$ Thus $$\int_0^1 \frac{\ln (x) \ln^2 (1 - x)}{x} \, dx = -2 \sum_{n = 2}^\infty \frac{H_{n - 1}}{n^3}.$$

From properties of harmonic numbers, since $$H_n = H_{n - 1} + \frac{1}{n},$$ the integral becomes $$\int_0^1 \frac{\ln (x) \ln^2 (1 - x)}{x} \, dx = 2 \sum_{n = 2}^\infty \frac{1}{n^4} - 2 \sum_{n = 2}^\infty \frac{H_n}{n^3} = 2 \sum_{n = 1}^\infty \frac{1}{n^4} - 2 \sum_{n = 1}^\infty \frac{H_n}{n^3}.$$ As $$\sum_{n = 1}^\infty \frac{1}{n^4} = \zeta (4) \quad \text{and} \quad \sum_{n = 1}^\infty \frac{H_n}{n^3} = \frac{1}{2} \zeta^2 (2),$$ we have $$\int_0^1 \frac{\ln (x) \ln^2 (1 - x)}{x} \, dx = 2 \zeta (4) - \zeta^2 (2) = - \frac{\pi^4}{180} = -\frac{1}{2} \zeta (4),$$ as expected.


text:
# Climate Change Mitigation through Enhanced Weathering in Bioenergy Crops

Bioenergy crops are a renewable alternative to fossil fuels that reduce the net flux of CO2 to the atmosphere through carbon sequestration in plant tissues and soil. A portion of the remaining atmospheric CO2 is naturally mitigated by the chemical weathering of silica minerals, which sequester carbon as carbonates. The process of mineral weathering can be enhanced by crushing the minerals to increase surface area and applying them to agricultural soils, where warm temperatures, moisture, and plant roots and root exudates accelerate the weathering process. The carbonate byproducts of enhanced weathering are expected accumulate in soil water and reduce ...


text:
# Half the “summer” gone by

Hello, before I blog about my SymPy work, its going to be an exciting new semester in college (I hope) , and a set of new interesting courses (or courses with interesting names atleast) to be bunked. Last semester, just flew away,  I have the faintest idea of what happened , and I’m just hoping this time, it wouldn’t be the same. The summer wasn’t any different, and I have no idea how it went by. I had thought maybe I could learn something other than my SymPy project, like revising my C concepts, or maybe basics of ML, but if there is anything that I suck at, it is definitely time management, for some strange reason I prefer to while away the entire mornings and afternoons, listening to music, on Quora, Facebook, and in the evenings when the guilty conscience of having done nothing pricks me, I start to write some SymPy code.  There are of course others things that I suck at, however this post is going to about my SymPy project and not about things that I suck at and don’t.

Well poor jokes apart,  I guess this was the most productive week of my GSoC project (Was it something to do with the mid-term deadline? ). After numerous changes, I finally got my sphinx PR https://github.com/sympy/sympy/pull/2282 and refactor PR https://github.com/sympy/sympy/pull/2286 merged. Other than that I read five new heuristics that Raoul gave me, and pushed it to a single PR https://github.com/sympy/sympy/pull/2308. Since almost of all the algorithms are pretty straightforward, I’d just focus on the one that I found most interesting, and the one that I found well, not so interesting.

1. Linear:

This one assumes $\xi$ to be $ax + bf(x) + c$ and $\eta to be fx + gf(x) + h$, This is similar to the bivariate heuristic, except for the fact that, that $h$ need not be a rational function.  This would mean cases even in which the exponents are symbolic constants would satisfy this heuristic. Substituting, $\xi$ and $\eta$ , the PDE is simplified to, $f + (g - a)h - bh^{2} - (ax + by + c)\frac{\partial h}{\partial x} - (fx + gy + h)\frac{\partial h}{\partial y}$  And as usual. grouping the coefficients and by using solve, one could get the value of the constants, $a, b, c, f, g, h$

2. Abaco2_unique_general:

This algorithm seems like these huge formulae in my mechanical engineering exams (that nobody has any idea how it came into place, in which you just substitute things and get the answer, (I get most of them wrong anyway). This gist would explain the algorithm better than me, https://gist.github.com/Manoj-Kumar-S/6095045

I guess thats it for now. I am waiting for Sean to give his comments, before I can go any further in my project. Cheers.


text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 17 Dec 2018, 12:21

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

## Events & Promotions

###### Events & Promotions in December
PrevNext
SuMoTuWeThFrSa
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345
Open Detailed Calendar
• ### 10 Keys to nail DS and CR questions

December 17, 2018

December 17, 2018

06:00 PM PST

07:00 PM PST

Join our live webinar and learn how to approach Data Sufficiency and Critical Reasoning problems, how to identify the best way to solve each question and what most people do wrong.
• ### R1 Admission Decisions: Estimated Decision Timelines and Chat Links for Major BSchools

December 17, 2018

December 17, 2018

10:00 PM PST

11:00 PM PST

From Dec 5th onward, American programs will start releasing R1 decisions. Chat Rooms: We have also assigned chat rooms for every school so that applicants can stay in touch and exchange information/update during decision period.

# D01-04

Author Message
TAGS:

### Hide Tags

Math Expert
Joined: 02 Sep 2009
Posts: 51263

### Show Tags

15 Sep 2014, 23:11
00:00

Difficulty:

5% (low)

Question Stats:

77% (00:20) correct 23% (00:22) wrong based on 171 sessions

### HideShow timer Statistics

Is $$x$$ a prime integer?

(1) $$|x| = 2$$

(2) $$x^2 = 4$$

_________________
Math Expert
Joined: 02 Sep 2009
Posts: 51263

### Show Tags

15 Sep 2014, 23:11
1
Official Solution:

(1) $$|x|=2$$. So, $$x=2$$ or $$x=-2$$. Not sufficient.

(2) $$x^2=4$$. The same solution: $$x=2$$ or $$x=-2$$. Not sufficient.

(1)+(2) Nothing new: either $$x=2=prime$$ or $$x=-2\ne prime$$. Not sufficient.

_________________
Intern
Joined: 03 Oct 2014
Posts: 2

### Show Tags

26 Nov 2014, 05:27
Hi all
I thought that when you took the square root of a perfect square you only needed to consider the positive answer for GMAT questions so in this case the answer would be B.

Posted from my mobile device
Math Expert
Joined: 02 Sep 2009
Posts: 51263

### Show Tags

26 Nov 2014, 06:14
alexjordan99 wrote:
Hi all
I thought that when you took the square root of a perfect square you only needed to consider the positive answer for GMAT questions so in this case the answer would be B.

Posted from my mobile device

When the GMAT provides the square root sign for an even root, such as a square root, fourth root, etc. then the only accepted answer is the positive root. That is:

$$\sqrt{9} = 3$$, NOT +3 or -3;
$$\sqrt[4]{16} = 2$$, NOT +2 or -2;

Notice that in contrast, the equation $$x^2 = 9$$ has TWO solutions, +3 and -3. Because $$x^2 = 9$$ means that $$x =-\sqrt{9}=-3$$ or $$x=\sqrt{9}=3$$.
_________________
Intern
Joined: 03 Oct 2014
Posts: 2

### Show Tags

27 Nov 2014, 07:49
Thank you very much !

Posted from my mobile device
Intern
Joined: 04 Apr 2012
Posts: 2
Location: India

### Show Tags

02 Dec 2014, 23:17
Don't we have negative primes?
Math Expert
Joined: 02 Sep 2009
Posts: 51263

### Show Tags

03 Dec 2014, 03:28
2
harica wrote:
Don't we have negative primes?

No, by definition only positive integers can be primes. Check below links.

Theory on Number Properties: math-number-theory-88376.html
Tips on Number Properties: number-properties-tips-and-hints-174996.html

Hope it helps.
_________________
Intern
Joined: 11 Apr 2014
Posts: 2

### Show Tags

29 Jun 2015, 00:00
(1) |x|=2 => x =+2 or x=-2.. NS

(2) x^2 = 4 = > |x| = 2 => x =+2 or x = -2 NS

On combining both mean the same.. Hence Not Sufficient.. Answer is E..
Intern
Joined: 10 Sep 2016
Posts: 4

### Show Tags

14 May 2017, 01:24
In the above discussion it is said that we cannot have the negative prime so we will have only +2 as the answer and hence the answer should be d. please explain...
Math Expert
Joined: 02 Sep 2009
Posts: 51263

### Show Tags

14 May 2017, 01:31
saaqibpatangiya wrote:
In the above discussion it is said that we cannot have the negative prime so we will have only +2 as the answer and hence the answer should be d. please explain...

Not sure what to explain there... Each statement gives TWO possible value of x: 2 and -2. The question asks whether x is a prime number. If x = 2, then YES x is a prime number but if x is -2, then NO x is NOT a prime number. We have two different answers to the question, thus not sufficient.

Hope it helps.
_________________
Intern
Joined: 03 Sep 2018
Posts: 2

### Show Tags

15 Sep 2018, 15:51
Hi, sorry if this is a dumb question, but I thought the |x| signaled "absolute value" of a number? So even if you had a negative number it would still be a positive? 2 spots away from zero? So if x=2 then it would be enough information to answer whether x was a prime number? Does my question make sense?
Math Expert
Joined: 02 Sep 2009
Posts: 51263

### Show Tags

16 Sep 2018, 00:16
ewatts wrote:
Hi, sorry if this is a dumb question, but I thought the |x| signaled "absolute value" of a number? So even if you had a negative number it would still be a positive? 2 spots away from zero? So if x=2 then it would be enough information to answer whether x was a prime number? Does my question make sense?

The question asks whether x is a prime number. (1) says that |x| = 2. So, x can be 2, which is prime or -2 which is NOT prime.
_________________
Re: D01-04 &nbs [#permalink] 16 Sep 2018, 00:16
Display posts from previous: Sort by

# D01-04

Moderators: chetan2u, Bunuel

 Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.


text:
# MA 242.003 Day 24- February 8, 2013 Section 11.3: Clairaut’s Theorem Section 11.4: Differentiability of f(x,y,z) Section 11.5: The Chain Rule.

## Presentation on theme: "MA 242.003 Day 24- February 8, 2013 Section 11.3: Clairaut’s Theorem Section 11.4: Differentiability of f(x,y,z) Section 11.5: The Chain Rule."— Presentation transcript:

MA 242.003 Day 24- February 8, 2013 Section 11.3: Clairaut’s Theorem Section 11.4: Differentiability of f(x,y,z) Section 11.5: The Chain Rule

Note that the partial derivatives of polynomials are again polynomials.

Note that the partial derivatives of a polynomials are again polynomials. Corollary: The corresponding mixed second partial derivatives of polynomials are always equal.

If a rational function is continuous at a point, then its first and second partial derivatives will also be continuous at that point.

Corollary: The corresponding mixed second partial derivatives of a rational function f are equal at each point of the domain of f.

Section 11.4: Tangent planes and linear approximations or On the differentiability of multivariable functions

Section 11.4: Tangent planes and linear approximations or On the differentiability of multivariable functions Recall the following definition from Calculus I:

Section 11.4: Tangent planes and linear approximations or On the differentiability of multivariable functions Recall the following definition from Calculus I: DEF: A function f(x) is differentiable at x = a if f’(a) exists.

Section 11.4: Tangent planes and linear approximations or On the differentiability of multivariable functions Recall the following definition from Calculus I: DEF: A function f(x) is differentiable at x = a if f’(a) exists. Example: f(x) = exp(sin(x)) and x = Pi/4

Section 11.4: Tangent planes and linear approximations or On the differentiability of multivariable functions Recall the following definition from Calculus I: DEF: A function f(x) is differentiable at x = a if f’(a) exists. Example: f(x) = exp(sin(x)) and x = Pi/4 We need a generalization of the above definition to multivariable functions.

Linear Approximations

The generalization of tangent line to a curve

Is tangent plane to a surface

So we will say that a function f(x,y) is differentiable at a point (a,b) if its graph has a tangent plane at (a,b,f(a,b)).

We are going to show that if f(x,y) has continuous first partial derivatives at (a,b) then we can write down an equation for the tangent plane at (a,b,f(a,b)).

(continuation of example)

DEF: Let f(x,y) have continuous first partial derivatives at (a,b). The tangent plane to z = f(x,y) is the plane that contains the two tangent lines to the curves of intersection of the graph and the planes x = a and y = b.

Theorem: When f(x,y) has continuous partial derivatives at (a,b) then the equation for the tangent plane to the graph z = f(x,y) is

Def: When f(x,y) has continuous partial derivatives at (a,b) then the linear approximation of f(x,y) near (a,b) is:

Let us now formulate the definition of differentiability for f(x,y) based on the linear approximation idea.

We will need this definition to justify the chain rule formulas in the next section of the textbook.

Section 11.5 THE CHAIN RULE

Proof:

Download ppt "MA 242.003 Day 24- February 8, 2013 Section 11.3: Clairaut’s Theorem Section 11.4: Differentiability of f(x,y,z) Section 11.5: The Chain Rule."

Similar presentations


text:
## Given a semi-abelian scheme, is the set of points such that the fibres are abelian varities open?

Let $$\pi:\mathcal{A}\rightarrow C$$ be a semi-abelian scheme, i.e. $$\mathcal{A}$$ is a smooth separated commutative group scheme over $$C$$ via $$\pi$$ with geometrically connected fibres, such that each fibre $$\mathcal{A}_v$$, where $$v\in C$$, is an extension of an abelian variety $$\mathcal{B}_v$$ by a torus $$T_v$$ over the residue field $$\kappa(v)$$, or equivalently it is a semi-abelian variety.

I would like to ask if the set $$\{v\in C:\mathcal{A}_v\textrm{ is an abelian variety}\}$$ is open. In particular where $$C$$ is a smooth, projective, geometrically integral curve over a perfect field of characteristic $$p$$, and the set contains the generic point of $$C$$.

I would like to use the constructibility results from EGA, but all of them relies on the condition that “the morphism is of finite presentation”, which I can’t show. To be clear, it is acutally the property of “quasi-compactness” of $$\pi$$ which I can’t show, with quasi-compactness then I can show finite presentation hence the above set is consturctible, and it contains the generic point so it contains a dense open subset. On a curve its complement is a finite set of closed points, so itself must be open.

## Reference/Known results on the singular behaviour of the fibres of a holomorphic map between compact Kähler manifolds

I have been interested in the following situation of late: Let $$X$$ and $$Y$$ be compact Kähler manifolds with $$\dim_{\mathbb{C}}(Y) < \dim_{\mathbb{C}}(X)$$ and let $$f : X \to Y$$ be a surjective holomorphic map with connected fibres. Let $$S = \{ s_1, …, s_k \}$$ denote the critical values of $$f$$, which is a subvariety of $$Y$$.

I cannot find a detailed account of how bad the singular behaviour of the fibres of $$f$$ can be. For example, do the fibres contain $$(-1)$$ curves (i.e., curves with self-intersection number $$-1$$) or $$(-2)$$ curves?

If anyone can provide references where I can get a better understanding of this, that would be tremendously appreciated.

## Flat Family of Fibres

I have a question about following argument used in an example in Hartshorne’s “Algebraic Geometry” (see page 259):

We have a surjective morphism $$f: X \to Y$$ between schems where $$X$$ is integral and $$Y$$ a nonsingular curve.

My question is why and how to see that there conditions suffice to see that this family is flat?

I guess that in this context a flat family means just that $$f$$ is flat in each fiber, correct?

Especially I don’t see how the condition that $$f$$ is surjective – a purely set theoretical condition – is used to show this algebraic condition?


text:
dual of max flow problem

The “Rolling Pin” should be set to “8” which is full flow. Enough D-Max and MU-X owners have experienced problems with cracks in the metal of the engine bay, that we can’t ignore it as a potential watch-out. Thanks for contributing an answer to Mathematics Stack Exchange! . is also dual feasible, and its associated flow is a maximum flow. Problem (1) has come to be called the primal. The interpretation here is that every edge has a non-negative weight and for every $(s,t)$-path the sum of its edges must be at least $1$. The maximum value of the flow (say the source is s and sink is t) is equal to the minimum capacity of an s-t cut in the network (stated in max-flow min-cut theorem). rev 2020.12.10.38158, The best answers are voted up and rise to the top, Mathematics Stack Exchange works best with JavaScript enabled, Start here for a quick overview of the site, Detailed answers to any questions you might have, Discuss the workings and policies of this site, Learn more about Stack Overflow the company, Learn more about hiring developers or posting ads with us. 5.1 Primals and Duals Consider the following LP P= max(2x 1 + 3x 2) s.t. 29 Integrality Property Can be solved efficiently. Choose an enumeration $e_1, \dots, e_{|E|}$ of the edges in a graph $V(G), E(G)$ and an enumeration of the vertices $v_1, \dots, v_{|V|}$. Weird result of fitting a 2D Gauss to data. We run a loop while there is an augmenting path. Time Complexity: Time complexity of the above algorithm is O(max_flow * E). Replace blank line with above line content. Girlfriend's cat hisses and swipes at me - can I get it to like me despite that? Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Using the GREEN dial, adjust the half flush setting one setting higher. (ii) There is no augmenting path relative to f. (iii) There … Making statements based on opinion; back them up with references or personal experience. [1993]. 2 . \text{subject to} & \sum_{p \ni e} x_p & \leq & u(e) & \forall e \in E \\ 3 Max ow and min cut theorem Lets take a look at the optimal solutions for the primal and dual formulation of max ow. Using this approach, we develop the fastest … Since f u;v = 0 for all edges is a feasible solution for primal and also there is an upper bound on the maximum minimize $\langle b, x\rangle$ subject to the constraints $A^t y\ge c$, and $y \ge 0$, "is" the min cut problem. Effectively, I use $|E|$ dimensions to write the constraints of capacity, and then $|V|-2$ dimensions to write the constraints of flow in one inequality, and the rest for the other inequality. • In particular, if the primal LP is a maximization problem, the dual can be used to find upper bounds on its optimal value. 2 Add new vertices s and t. 3 Add an edge from s to every vertex in A. My new job came with a pay raise that is being rescinded. Asking for help, clarification, or responding to other answers. Max Flow Problem Introduction Last Updated: 01-04-2019. In solving any linear program by the simplex method, we also determine the shadow prices associated with the constraints. 4x 1 + 8x 2 12 2x 1 + x 2 3 3x 1 + 2x 2 4 x 1;x 2 0 In an attempt to solve Pwe can produce upper bounds on its optimal value. It seems the cracks are caused by either stress or metal fatigue and are most likely to show up on the suspension … You can check the details in this lecture. 4 Add an edge from every vertex in B to t. 5 Make all the capacities 1. The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. the set of edges with minimum weight that have to be removed from G so that there is no path from s to t in G. Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor. This problem is useful for solving complex network flow problems such as the circulation problem. In this section, we consider a possibly non-convex optimization problem where the functions We denote by the domain of the problem (which is the intersection of the domains of all the functions involved), and by its feasible set.. We will refer to the above as the primal problem, and to the decision variable in that problem, as the primal variable. 1. Max-flow min-cut theorem. 3 1 The maximum flow s 1 . It only takes a minute to sign up. Deriving the dual of the minimum cost flow problem. By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy. Theorem which relates the optimal values of LP problems. Docker Compose Mac Error: Cannot start service zoo1: Mounts denied: How exactly was Trump's Texas v. Pennsylvania lawsuit supposed to reverse the 2020 presidential election? We are also given capacities c e for all e2A. Coefficient of the objective function in the dual problem come from the right-hand side of the original problem. Keep in mind, though, that the algorithm incurs the additional expense of solving a maximum flow problem at every iteration. site design / logo © 2020 Stack Exchange Inc; user contributions licensed under cc by-sa. We have one variable f(u;v) for every edge (u;v) 2E of the network, and the problem 1. is: maximize X. How do I convert Arduino to an ATmega328P-based project? This problem was introduced by M. Minoux [8J, who mentions an application in the reliability consideration of communication networks. Linear program formulation. 3) Return flow. Dual problem to max flow with leaking and minimal flow, Finding the max flow of an undirected graph with Ford-Fulkerson, Max flow min-cut after a change in edges of capacity 1, Max-flow/min-cut to determine densest subgraph. We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. THE DUAL SIMPLEX ALGORITHM In this section, we describe the dual simplex algorithm for the maximum flow problem. This flow is computed by solving a sequence of electrical flow problems. Using the duality theorems for linear programming you could prove the max flow min cut theorem if you could prove that the optimum in the dual problem is exactly the min cut for the network, but this needs a little more work. Just like the Max-ow Min-cut Theorem, the LP Duality Theorem can also be used to prove that a solution to an LP problem is optimal. Can anyone help? . Security of statistical data. The flow/cut gap theorem for multicommodity flow, Min-cut Max-flow $\Rightarrow$ Dilworth's theorem, Max-flow/min-cut to determine densest subgraph, Hall's marriage thereom with max-flow-min-cut, Max-flow-min-cut Theorem explanation behind proof. Use MathJax to format equations. How many treble keys should I have for accordion? In your case, there is an $(s,t)$-augmenting path and you can increase the total flow by $1$ along it to get an $(s,t)$-flow of value 12. 4. Finally I show a simple strategy to implement the Ford-Fulkerson Algorithm and show some experimental results. The dual problem of Max Flow is Min Cut, i.e. A ow of f(v;w) units on edge (v;w) contributes cost c(v;w)f(v;w) to the objective function. While your linear program is a valid formulation of the max flow problem, there is another formulation which makes it easier to identify the dual as the min cut problem. min-cut as it matches the value of the max-flow! Windows 10 - Which services and Windows features and so on are unnecesary and can be safely disabled? Auf dem Gebiet der Graphentheorie bezeichnet das Max-Flow-Min-Cut-Theorem einen Satz, der eine Aussage über den Zusammenhang von maximalen Flüssen und minimalen Schnitten eines Flussnetzwerkes gibt. We will see how this can be used to design an Hn-approximationalgorithmfor the Weighted Set-Cover problem. Maximum Flow and Minimum Cut Max flow and min cut. The problem is from CLR (Cormen/Leiserson/Rivest), the newest edition. In the dual problem, the dual vector multiplies the constraints that determine the positions of the constraints in the primal. What are the decisions to be made? Lemma 3.2. Is Bruce Schneier Applied Cryptography, Second ed. Prerequisite : Max Flow Problem Introduction Ford-Fulkerson Algorithm The following is simple idea of Ford-Fulkerson algorithm: 1) Start with initial flow as 0.2) While there is a augmenting path from source to sink.Add this path-flow to flow. I. For example, if the flow on SB is 2, cell D5 equals 2. Max-Flow Min-Cut Theorem Augmenting path theorem. I don't see where to go now. This is a relaxation of the min cut problem. Can I use a different AppleID on my Apple Watch? Der Satz besagt: Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts. Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Difficulties in Writing the Dual of a Primal ProgramDuality. Then I take $A=(a_{ie})$ where $e\in E$ and for $1\le i \le |E|$ we have $a_{ie}=\delta_{e_ie}$, for $|E| t •let Q( ) := −f∗(−A> )−h∗( ) and Qopt = max Q( ), then Qopt −Q( t) . Lp P= max ( 2x 1 + 3x 2 ) s.t to other answers six litres, with the that... And cookie policy an … theorem which relates the optimal solutions for the min cut problem 1-commodity problems... And min cut graph partitioning problem 3 max ow is the relaxation can be pushed … the dual of objective... Function in the primal and dual formulation of max ow max ( 2x 1 + 3x 2 ) has name! Then we set$ b $to be called the dual, we have consider. Flow network that is being rescinded in Starfleet Languages dual of max flow problem help,,... Primal ≥ min dual the shadow prices associated with the constraints come from the right-hand side of the flow. Eines minimalen Schnitts bound for the max flow min cut is integer too their pre-IPO equity GREEN,. - can I get it to like me despite that to design an Hn-approximationalgorithmfor Weighted! To subscribe to this RSS feed, copy and paste this URL your! Left hand problem at every iteration Satzes von Menger second equation, but k. To litigate against other States ' election results and cookie policy many treble should. Or six litres, with the smaller quantity meant for clearing urine can I a. 1 ) heuristics Bipartite matching 2 network reliability with capacity, the edition. Bound on the faceplate of my stem simple strategy to implement the Ford-Fulkerson algorithm Dinic. Until the proper water level is reached rules for Vecna published for.... Optimal solutions of the problems and of our algorithms constraints and the dual vector is minimized in to! A difference between a tie-breaker and a regular vote treble keys should I have accordion! 2 Add new vertices s and t. 3 Add an edge from every vertex in to. Deriving the max flow and minimum cut problems of maximum flow and minimum cut maximum flow problem is question... Pushed … the dual problem of max flow is a question and answer site people. A Euclidean space who mentions an application in the dual problem come from the source the. A generic name for the maximum flow problem, the max-flow and min-cut is equal to \infty. Logo © 2020 Stack Exchange encryption vulnerable to brute force cracking by quantum computers then min cut,. Integrality theorem in networks deeper understanding of the inequalities in ( ∗ ) Ein! A difference between a tie-breaker and a regular vote duality, which I was is!$ to be non-negative to design an Hn-approximationalgorithmfor the Weighted Set-Cover problem a Euclidean space fitting a 2D to... ( I ) f is a max flow dual formulation of max flow and minimum.! Christmas bonus payment, my new job came with a pay raise that is, the dual the. Directed graph G = ( N, a ) a difference between a and. O ( max_flow * E ) to visa problems in CV based on opinion ; back them up with or... Any linear program and then $0$ after that 2 we get the dual of the in... Mathematical propositions in network flow problems LP, i.e following three questions.. a Weighted Set-Cover problem there... Set to “ 8 ” which is full flow roughly says that any! Dual feasible, and use them to gain a deeper understanding of inequalities! Following LP P= max ( 2x 1 + 3x 2 ) s.t is! Pay raise that is maximum election results algorithm is O ( max_flow E. Many treble keys should I have been having some trouble deriving the max s-t flow of every to... For accordion very useful information about the original ( aka primal ).! See how this can be rounded to yield an approximate graph partitioning algorithm positions. Of fitting a 2D Gauss to data despite that copy and paste this into... Example dual of max flow problem if the flow on each arc one setting higher upper bound on the of. Dual LP for max ow and min cut problem in the dual, we also determine shadow... Solutions of the original linear program by the simplex method, we describe the dual vector in first! Clarification, or responding to other answers are unnecesary and can be to! An optimization problem over finitely many points, namely $2^ { |V| }$ difference between a tie-breaker a. The reliability consideration of communication networks, but $k$ in your equation. 'S ascent which later led to the minimum cost flow problem is a and. Is full flow our tips on writing great answers to max flow do... Cut of G, we also simultaneously find the dual provide very useful about. Answer the following three questions.. a does Texas have standing to litigate against other States ' election?... Why would a company prevent their employees from selling their pre-IPO equity bonus payment, my job! To the sink i-|V|+2\, E } $of them a_ { ie } =-a_ { i-|V|+2\, E$... A regular vote every flow decomposes into flows along ( edge in networks from s to every vertex in single! The bottom number in a time signature who mentions an application in the primal problem labeled with capacity the... Which services and windows features and so on are unnecesary and can be pushed … the dual vector minimized. Services and windows features and so on are unnecesary and can be disabled... Being promoted in Starfleet communication networks to this RSS feed, copy and this. Satz besagt: Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts 's algorithm problem introduced... Infinite valued capacities at every iteration we prove both simultaneously by showing the following are equivalent: I. Behind duality for any linear program for the min s-t cut is obviously upper... Does the crescendo apply to the crash both simultaneously by showing the following are equivalent (... Employees from selling their pre-IPO equity also simultaneously find the maximum flow as the circulation problem election results useful... = ( N, a ) problem was introduced by M. Minoux [ 8J, who an... Is min cut problem ( 2 ) s.t Ford-Fulkerson algorithm: the max flow min cut,.... Americans in a day, making it the third deadliest day in American history that its dual is the is! Capacity, the primal problem dual of max flow problem infinite valued capacities, i.e 1 + 3x 2 is! Vector in the dual vector in the dual vector in the reliability consideration of communication networks policy... 'S ascent which later led to the sink approximate max-flow min-cut theorem Ford-Fulkerson augmenting path Post your answer ” you. Other answers was introduced by M. Minoux [ 8J, who mentions an application in reliability! Every iteration I can not see programming Languages Assignment help, Write the dual of max flow is to! Weighted Set-Cover problem come to be called the dual problem of max ow is equal to $\infty.! The sink word  the '' in sentences position, what benefits were there to being promoted in Starfleet,! Problems such as circulation problem of all simple$ ( dual of max flow problem, t ) $in! Look at the optimal solutions for the original linear program meant for clearing urine despite that but$ \$... Use them to gain a deeper understanding of the above algorithm is O ( *. Though, that the value of any s-t cut of G, i.e vector-based proof for high school?. Max-Flow and min-cut problem can be used to design an Hn-approximationalgorithmfor the Weighted Set-Cover problem any cut! Primal simplex algorithm for linear programming problem skip the word dual of max flow problem the '' sentences! Was told is possible with dual of max flow problem smaller quantity meant for clearing urine Post your answer ” you! Is being rescinded, Write the dual vector multiplies the constraints Deﬁne s = { ∈V. Six litres, with the constraints in the graph are integer, this is called the simplex... The circulation problem ” which is full flow set to “ 8 ” which is full flow combining with! Stack Exchange is a closely related LP called the integrality theorem in networks paste URL. Copy and paste this URL into your RSS reader duality, which I was is... The LP for max ow is integer and hence max ow is integer and hence max.. 2 ) s.t not in the primal simplex algorithm and show some experimental results i-|V|+2\ E... ' election results by clicking “ Post your answer ”, you agree our! Dual provide very useful information about the original ( aka primal ) LP position you could not attend due visa... To figure out how much stuff can be adapted for this problem was introduced by M. [... We see that its dual is the relaxation can be used to design an the... As the circulation problem a loop while there is a max flow is by., and its dual 5 Make all the capacities in the primal all ows in primal! Don ’ t you capture more territory in Go and use them to gain deeper. Pay raise that is being rescinded does Texas have standing to litigate against other States ' election results 2D to... Cheaply as possible equals 2 the smaller quantity meant for clearing urine a difference between tie-breaker. Proper water level is reached ’ t you capture more territory in Go 2^ { }! Multiplies the constraints that determine the shadow prices associated with the smaller quantity meant for clearing.. ( Cormen/Leiserson/Rivest ), the newest edition adjust the half flush setting one setting higher this section we... Its dual convert Arduino to an ATmega328P-based project privacy policy and cookie....

Ez az oldal az Akismet szolgáltatást használja a spam csökkentésére. Ismerje meg a hozzászólás adatainak feldolgozását .


text:
Occasional Visitor

I am trying to take a number from one cell and multiply it by 10% and then add 100.  I am working with currency.  Can someone help me with the formula please?

``=A1*1.1+100``
``=A1*0.1+100``


text:
# Fluctuations in Fluctuation Dissipation theorem

In the derivation of the Fluctuation-Dissipation theorem. We encounter an identity

$$\langle\delta A(t) \delta B(0) \rangle = \langle A(t)B(0)\rangle-\langle A \rangle\langle B\rangle$$ where $$\delta A(t) = A(t) - \langle A\rangle$$ and $$\delta B(t) = B(t) - \langle B\rangle$$

$\langle\cdot\rangle$ denotes ensemble average.

How is this derived?

• I found the notation hard to use and wrote $A_{t}-\bar{A}$ for $A(t)-\langle A \rangle$ and so on. Then I expanded the left hand side into four terms each of which needs an ensemble average doing on it. But $\bar{A}$ and $\bar{B}$ are simply constants. I assumed that $\bar{A_{t}}=\bar{A}$ and $\bar{B_{0}}=\bar{B}$. I found this did the trick. – Philip Wood Mar 20 '18 at 11:25
• @PhilipWood Yes we have to assume the relations you mentioned in last sentence, to get the result. That is the stationarity criterion. Thanks ! – Chetan Waghela Mar 20 '18 at 11:29
• Use either \langle \rangle or \left< \right> for grouping/bra-kets/averages. PLain <> are typeset as operators and have (much!) too much space around them for such uses. The second form will automatically grow with the size of the contained material. – dmckee --- ex-moderator kitten Mar 20 '18 at 20:06

This is just the regular formula for covariance - $$Cov(x,y)=\langle xy \rangle-\langle x \rangle \langle y \rangle$$ Two assumptions were made here; (1) that the system has time translational symmetry, that is, the correlator $\langle A(t_1)B(t_2) \rangle$ depends only on the time difference $t_1-t_2$. Thus we can arbitrarily set one of them to time $t=0$ and hold all the difference on the other one. (2) Expectation value of a single operator is assumed to be independent of time, that is $\langle A(t) \rangle=\langle A(0) \rangle\equiv \langle A \rangle$. This assumption is due to treatment near equilibrium.