text:
Show Summary Details
More options …

# High Temperature Materials and Processes

Editor-in-Chief: Fukuyama, Hiroyuki

Editorial Board: Waseda, Yoshio / Fecht, Hans-Jörg / Reddy, Ramana G. / Manna, Indranil / Nakajima, Hideo / Nakamura, Takashi / Okabe, Toru / Ostrovski, Oleg / Pericleous, Koulis / Seetharaman, Seshadri / Straumal, Boris / Suzuki, Shigeru / Tanaka, Toshihiro / Terzieff, Peter / Uda, Satoshi / Urban, Knut / Baron, Michel / Besterci, Michael / Byakova, Alexandra V. / Gao, Wei / Glaeser, Andreas / Gzesik, Z. / Hosson, Jeff / Masanori, Iwase / Jacob, Kallarackel Thomas / Kipouros, Georges / Kuznezov, Fedor

IMPACT FACTOR 2018: 0.427
5-year IMPACT FACTOR: 0.471

CiteScore 2018: 0.58

SCImago Journal Rank (SJR) 2018: 0.231
Source Normalized Impact per Paper (SNIP) 2018: 0.377

Open Access
Online
ISSN
2191-0324
See all formats and pricing
More options …
Volume 38, Issue 2019

# The effect of MgTiO3Adding on Inclusion Characteristics

Xu Chen
• School of Metallurgical Engineering, Anhui University of Technology, Maanshan, Anhui, 243002, P R China
• Key Laboratory of Metallurgical Emission Reduction & Resources Recycling (Anhui University of Technology), Ministry of Education, Maanshan, Anhui, 243002, P R China)
• Other articles by this author:
/ Zhang Mingya
• School of Metallurgical Engineering, Anhui University of Technology, Maanshan, Anhui, 243002, P R China
• Key Laboratory of Metallurgical Emission Reduction & Resources Recycling (Anhui University of Technology), Ministry of Education, Maanshan, Anhui, 243002, P R China)
• Other articles by this author:
/ Li Jianli
• The State Key Laboratory of Refractories and Metallurgy, Wuhan University of Science and Technology, Wuhan, Hubei, 430081, P R China
• Key Laboratory of Metallurgical Emission Reduction & Resources Recycling (Anhui University of Technology), Ministry of Education, Maanshan, Anhui, 243002, P R China)
• Other articles by this author:
/ Ran Songlin
• School of Metallurgical Engineering, Anhui University of Technology, Maanshan, Anhui, 243002, P R China
• Key Laboratory of Metallurgical Emission Reduction & Resources Recycling (Anhui University of Technology), Ministry of Education, Maanshan, Anhui, 243002, P R China)
• The State Key Laboratory of Refractories and Metallurgy, Wuhan University of Science and Technology, Wuhan, Hubei, 430081, P R China
• Other articles by this author:
/ Shan Mengwei
• School of Metallurgical Engineering, Anhui University of Technology, Maanshan, Anhui, 243002, P R China
• Key Laboratory of Metallurgical Emission Reduction & Resources Recycling (Anhui University of Technology), Ministry of Education, Maanshan, Anhui, 243002, P R China)
• Other articles by this author:
/ Yue Qiang
• School of Metallurgical Engineering, Anhui University of Technology, Maanshan, Anhui, 243002, P R China
• Other articles by this author:
/ Kong Hui
• Corresponding author
• School of Metallurgical Engineering, Anhui University of Technology, Maanshan, Anhui, 243002, P R China
• Key Laboratory of Metallurgical Emission Reduction & Resources Recycling (Anhui University of Technology), Ministry of Education, Maanshan, Anhui, 243002, P R China)
• Email
• Other articles by this author:
Published Online: 2019-05-11 | DOI: https://doi.org/10.1515/htmp-2019-0004

## Abstract

MgTiO3 powder was directly added into molten steel at 1873K, and its effect on inclusion characteristics was studied by a scanning electron microscope and an energy dispersive spectrometer. Thermodynamic calculation indicates that MgTiO3 is unstable in molten steel and may decompose into [Ti], [O] and MgO. However, only Ti-bearing inclusions were observed in the treated sample, and Mg-bearing inclusions were absent. This can be explained by the features of wettability and stability for MgO. Compared with a Non-treated sample, both oxide and coarse MnS in treated sample were refined. For the oxide, this originates from the formation of Ti-bearing inclusion. For coarse MnS, this may be due to the fact that Ti can aggravate S segregation. Besides, this aggravation makes coarse MnS less globular. After etching, it was found that in the treated sample, Ti-bearing inclusion can induce the nucleation of intragranular acicular ferrites. This appearance was totally different from that of Non-treated sample, and indicates the effectiveness of external adding method in oxide metallurgy.

PACS: 81.30.Mh

## 1 Introduction

In 1990, the concept of Oxides Metallurgy is proposed by Takamura and Mizoguchi [1]. Its key is to utilize fine inclusions to induce nucleation of intragranular acicular ferrite (IAF) during austenite-ferrite transformation. Because of the interlocking nature of IAF, its formation enhances both strength and toughness [2, 3].

Many kinds of inclusions have been suggested as effective sites for IAF nucleation, and their formation can be classified into Internal Precipitation Method (IPM) [4, 5] and External Adding Method (EAM) [6]. The former means that preferred inclusions generate either during de-oxidation or solidification processes. Thus precise control of steel composition and fine adjustment of production process are crucial. The latter means that pre-prepared particles are directly added into steel. So how to evenly distribute them in steel and make them as potential nucleation sites during phase transition is the focus of the research.

Recently, Ti-bearing and Mg-bearing inclusions have attracted much attention. The former is suggested as the most efficient inclusion for IAF nucleating, and the latter’s IAF nucleation effect is still under discussion. Thus, both of them are the hot topic of EAM study, and different methods have been developed, which is summarized respectively.

For Ti-bearing inclusion, three methods have been adapted. Firstly, Ti-bearing oxides and steel were bonded together at solid state [7, 8]. Secondly, Ti-bearing oxides were mixed with steel powder [9, 10] or put inside the hollow of steel cylinder [11, 12]. Then oxide and steel were melted almost simultaneously. Thirdly, Ti-bearing oxides were directly added into molten steel. For example, the

cored wire, which contains a high number density of oxides, was feed into molten steel by Grong et al. [13]. Moreover, different additives with metallic Ti and TiO2 were added into the steel melt just before casting or into the mold during casting to create Ti-bearing inclusions [14].

It can be seen that for the first and second methods, both as-sintered steel and co-melting of oxide and steel are totally different from actual steel-making process, which may limit their application. For the third method, the presence of acicular ferrite could not be confirmed definitely, and the holding time is required as short as possible to avoid particle floating.

For Mg-bearing inclusion, two methods have been adapted. Firstly, an approach for pre-dispersing MgO with AlSi alloy nanoparticleswas established, and the resulting nanoparticles were added into steel melt both in laboratory scale and real production [15, 16]. Secondly, chemical modification of the surface of MgO nanoparticles for steel-making was developed [17].

In this paper, MgTiO3 powder was introduced into molten steel for the first time to our knowledge. The aim is to utilize the decomposition reaction of MgTiO3 to release Mg/Ti into molten steel and play a role in IAF nucleation effect.

## 2 Experimental Procedure

The preparation of powder mixture consisted of two steps. Firstly, approximate MgTiO3 (Aladdin, purity > 99.9%, size < 2μm) and pure iron powder were weighted. Secondly, planetary ball milling was used to mix them for three hours in order to achieve homogeneous composition.

Commercial low-carbon steel (about 1500g) was used as raw material and put in an alumina crucible. The alumina crucible was located inside the graphite crucible in a high-heat tube-type resistance furnace. The experimental temperature was 1873K, and high purity argon gas was used as protecting gas during the melting experiment. The powder mixture was directly added into the molten steel and the mixture dissolved quick. Then after being held for 10 minutes at 1873K, the crucible was taken out. After solidification, steel sample was quenched into water. It should be mentioned that the surface of EAM-treated sample was smooth and no laminations were observed. Moreover, a comparison sample without EAM treatment was also prepared. The samples were sent to NCS Testing Technology Co., Ltd (China National Analysis Center for Iron and Steel) for composition analysis, and the content of Als and Ti were measured by the method of ICP-AES. The composition of both samples is shown in Table 1.

Table 1

Chemical composition of steel samples (mass percentage)

The morphology and composition of inclusions were characterized by scanning electron microscope (SEM: JSM-6510LV) and energy dispersive spectrometer (EDS: INCA Feature X-Max 20). In both samples, inclusions were classified as oxide and sulfide. The latter was pure MnS. In fact, MnS segregation, which heterogeneously nucleates on oxides, was also observed. This kind of inclusion was attributed as oxide.

The data processing for EDS point analysis was carried out following Wang Xinhua et al. [18]. Firstly, iron was excluded to eliminate the contribution of signals from steel matrix. Then oxygen was ruled out due to insufficient accuracy. Finally, the content of remaining elements was normalized to 100%, and reported in mass percentage. Beside point analysis, area mapping functions of EDS was also applied to intuitively characterize the distribution of each element in inclusion. This is helpful to reveal the inclusion complexity [19, 20, 21].

Software of INCA Feature was applied to automatically find and analyze inclusions in preselected area. It should be mentioned that the inclusion size is its Feret maximum, and the inclusion aspect ratio φ is the ratio of its Feret maximum to Feret minimum.

## 3 Results and discussion

Thermodynamic calculation of MgTiO3 in molten steel is carried out based on following equations [22, 23]:

(1)$TiO2(s)=[Ti]+2[O]ΔG2θ=−675600+234T J⋅mol−1$(2)

It should be mentioned that Ti in molten steel can form many oxides, such as TiO, Ti2O3, Ti3O5, and TiO2, and inconsistent results have been present. To simplify, equation (2) is applied. Thus, equation (3) can be derived:

$MgO⋅TiO2(s)=MgO(s)+[Ti]+2[O]ΔG3θ=−2946800+76.5T J⋅mol−1$(3)

If the activities of MgO·TiO2(s) and MgO(s) are assumed as unity and the activity of [Ti] is simplified as its mass percentage, the $\Delta {\text{G}}_{3}^{\text{θ}}$is negative in 1873K even though the mass percentage of [O] is 1. Thus the deposition of MgO·TiO2(s) in molten steel may occur, which releases [Ti], [O] and MgO at the same time. To confirm this effect, systematic inclusion analysis has been conducted.

Based on SEM-EDS mapping analysis, the figures of typical oxide are shown in Figure 1 ((a) for Non-treated sample and (b) for EAM-treated sample). In Non-treated sample, the oxide was Mn-Si-Al-O. For EAM-treated sample, the elements of Ti, Mn, Si, and Al coexisted in oxide, while element of Mg was not found. In fact, the similar results have been also observed in our previous studies in addition of TiO2 and MgO, respectively. To confirm this characteristic, statistically analysis for inclusion has been carried out by INCA Feature software. The total number of measured inclusions in EAM-Treated Sample was 2080. Among them, only 5 Mg-bearing inclusions were observed. For these Mg-bearing inclusions, the Mg contents were all below 1%, and their sizes were all smaller than 1μm. As for Ti-bearing oxide, its number was much larger. Considering accuracy, only the inclusion, whose size was larger than 1μm, was taken into account. The resulting number was 1310. Among them, 35% inclusions (number percentage) can be classified as Ti-bearing oxide, and their average content of Ti was 14%.

Figure 1

SEM micrographs and EDS mapping images of various elements for typical oxide (a) For Non-treated sample (b) For EAM-treated sample

Then a question should be answered: why only Ti-bearing inclusions were observed, nevertheless, Mg-bearing inclusions were absent? This can be explained by the wettability between molten steel and MgO.

In 2017, sessile drop method has been employed to study the wettability between liquid iron and sintered MgO substrate at 1823K by Ren et al. [24]. In their experiments, two iron samples were used, and their Al concentrations were 18 ppm and 370 ppm, respectively. The former sample’s results were used to analyze since the Al concentration in our sample was 21 ppm.

On the one hand, the stable contact angle between the sintered MgO substrate and the liquid iron was approximately 134 at 1823K. This means that in our sample with similar Al content, MgO is nonwetting with molten iron, and can easily float up. On the other side, EDS analysis indicated that the composition of iron sample surface after sessile drop experiment was relatively uniform Fe. However, the iron sample with 370 ppm Al was covered with an oxide layer. This hints that for the low Al sample, a reaction between MgO and liquid steel is difficult.

Based on upper two sides, the released MgO was absent in our sample. In fact, to introduce MgO into molten steel, special technology should be applied [15, 16, 17]. While for [Ti], it can easily react with other elements in molten steel, and simultaneously released [O] may accelerate these reactions. These lead to the formation of Ti-bearing oxides, which may refine the oxides.

To confirm this conclusion, the relationship between oxide size and number density in EAM-treated sample and Non-treated sample is present in Figure 2. Considering accuracy, only the oxide with size larger than 1μm,was taken into account. It can be seen that oxide was fined, and its number density was increased. This was consistent with upper analysis.

Figure 2

The relationship between oxide size and number density in EAM-treated sample and Non-treated sample

Except oxide, pure MnS was also observed in both samples, and their typical figures are shown in Figure 3 ((a) for Non-treated sample and (b) for EAM-treated sample). It’s known that due to high concentration of product (a[Mn]×a[S], a means the activity), MnS normally cannot form in molten steel. Based on origination, Zheng et al.’s [25] indicates that MnS may be classified as coarse (>1.5μm) and fine (<1μm). The former originates from the eutectic reaction during solidification, and the latter is attributed to the probable precipitation after complete solidification.

Figure 3

SEM micrographs and EDS mapping images for typical pure MnS (a) For Non-treated sample (b) For EAM-treated sample

Since the external adding method is closely related to solidification, coarse MnS was our focus.

The relationship between coarse MnS size and number density in the EAM-treated sample and non-treated sample is shown in Figure 4. It can be seen that with EAM treatment, coarse MnS was refined, and its number density was increased. Moreover, the number percentage (aspect ratio 1<φ<2) has decreased from 87.5 to 79.4, which means that the adding of MgTiO3 makes coarse MnS less globular.

Figure 4

The relationship between coarse MnS size and number density in EAM-treated sample and Non-treated sample

The contrary trend has been reported and explained by Zheng’s et al. [25]. They found that surfactants of Te can increase the percentage of coarse MnS (aspect ratio 1<φ<2) and decrease its number density. Based on their theory, our results can be well explained, which is shown bellowing in brief and divided into following five parts.

Firstly, Sulfur segregation is the key to MnS precipitation since S (partition coefficient ks = 0.05) [26] segregates much easier than Mn (ks = 0.76) [26] during solidification.

Secondly, since the content of Ti is only about 23 ppm, its effect on activity coefficient of Sulfur can be negligible.

Thirdly, since Ti doping decreases the surface tension of liquid iron [27], it preferentially accumulates at the liquid-solid steel interfaces as surfactant.

Fourthly, Zheng et al. [25] pointed out that due to fast solidification, solute concentration in the newly formed solid monolayer is in excess of the equilibrium solubility. Then, the solute will diffuse back to the liquid phase across the interface because of its supersaturated state. Thus it’s feasible to assume that surfactant, which accumulates at solid-liquid interface, could affect mass transfer rate across interface [28, 29].

Fifthly, the interaction between S and Ti is stronger than that of between Fe and S. This is confirmed by the negative interaction coefficient ${\text{e}}_{S}^{Ti}\left(-0.27,JSPS\right).$Based on Zheng’s discussions [25], this may increase vacant sites for adsorption, accelerating solute back-diffusion from the solid phase to the liquid phase across the solid-liquid interface. This would aggravate the segregation of Sulfur into the interdendritic regions, and increase its supersaturation.

Thus, Ti doping made coarse MnS less globular and higher density. This trend is contrary to Te doping effect. This is due to the fact that the interaction between S and Te is weaker than that of between Fe and S, which is contrary to Ti property.Moreover, since Te is extremely surface active in liquid steel [30], its effect on coarse MnS is more obvious than that of Ti.

Figure 5(b) describes SEM micrograph and EDS mapping images of typical Ti-bearing oxide in EAM-treated sample after etching in 3Vol%Nital solution. It can be seen that IAF plates initiates from a single Ti-bearing inclusion. This phenomenon was similar to the induced nucleation effect of Ti-bearing inclusion originating from IPM method [4], and totally different from that of Non-treated sample (shown in Figure 5(a)).

Figure 5

SEM micrograph and EDS mapping images for typical oxide after etching (a) For Non-treated sample (b) For EAM-treated sample

Figure 1(b) has indicated that with EAM treatment, Ti-bearing oxides were formed. Till now, different mechanisms have been proposed to explain the reasons why Ti-bearing inclusion can promote IAF nucleation [2], such as inert surface, lattice disregistry, thermal coefficient, and Mn-depletion zone (MDZ). Among them, MDZ mechanism has been widely accepted. This mechanism is based on the assumption that inclusions can absorb neighboring Mn atoms from Fe matrix. If a corresponding supplement isn’t applied, Mn depleted zone will be formed in Fe matrix around inclusion. This promotes the nucleation of ferrites since Mn element is the stabilizer of austenite.

In 2018, Li et al. [20] indicates that in Al-Ti-Mg killed steel with low Al content, MDZ is formed by the combined effect of the precipitation of MnS and diffusion of Mn atoms into TiOx and MgTiOx. In EAM-treated sample, Al content was as low as 21ppm and Ti-bearing oxide was also found. This hint that a similar absorption may occur, which promote acicular ferrite nucleation. While in the Non-treated sample, no Ti-bearing oxides were found. The difference of inclusion characteristic leads to the different microstructure in two samples.

## 4 Conclusion

MgTiO3 powder was directly added into molten steel, and its effect on inclusion characteristic has been explored. At 1873K, MgTiO3 may decompose into [Ti], [O] and MgO, which results in the formation of Ti-bearing complex inclusions and the refinement of oxide. While for MgO, its wettability and stability leaded to the absent of Mg-bearing inclusion. Compared with a Non-treated sample, coarse MnS in the EAM-treated sample became less globular and higher density. This may be interpreted by the fact that Ti can aggravate S segregation. After etching, IAF plates have been observed in the EAM-treated sample, which is induced by Ti-bearing inclusions. This appearance was consistent with the Ti-bearing inclusion originating from internal precipitation method, and indicates the effectiveness of external adding method in oxide metallurgy.

## Acknowledgement

This work was supported by the National Natural Science Foundation of China (No.51474001), the State Key Laboratory of Refractories and Metallurgy, Wuhan University of Science and Technology (No. G201710), Anhui Provincial Natural Science Foundation (No.1608085J10), Financial support for academic and technical leaders (No.2016H092), Open fund of Key Laboratory of Metallurgical Emission Reduction & Resources Recycling (KF17-3), and Anhui University of Technology graduate innovation research (No. 2017148).

## References

• [1]

J.Takamura and S. Mizoguchi, Proceedings of the sixth international iron and steel congress, Nagoya, 1(1990) 591-597. Google Scholar

• [2]

T. Koseki, and G.Thewlis, Mater. Sci. Technol., 21(2005) 867-879.

• [3]

X.L.Wan XL, R.Wei, and K.M.Wu, Mater. Charact., 61(2010) 726-731.

• [4]

J.-S.Byun, J.-H Shim, and Y.W Cho, Scripta Mater., 48(2003) 449-454.

• [5]

N.Kikuchi, S.Nabeshima, Y.Kishimoto, T.Matsushita, and S. Sridhar, ISIJ. Int., 47(2007) 1255-1264.

• [6]

W.Z.Mu, P.G.Jönsson, and K.Nakajima, High Temp. Mater. Proc. 36(2017) 309-325. Google Scholar

• [7]

J.M.Gregg, and H.K.D.H.Bhadeshia, Metall. Mater. Trans. A, 25(1994) 1603-1611.

• [8]

S.H.Zhang, N.Hattori, M.Enomoto, and T.Tarui, ISIJ. Int., 36(1996) 1301-1309.

• [9]

W.Z.Mu, P.G.Jönsson, and K.Nakajima, ISIJ. Int., 52(2014) 2907-2916. Google Scholar

• [10]

W.Z.Mu, P.G.Jönsson, H.Shibata, and K.Nakajima, STEEL RES INT, 87(2016), 339-348.

• [11]

J.M.Gregg, and H.K.D.H.Bhadeshia, Acta Mater., 45(1997) 739-748.

• [12]

S.H.Nedjad, and A.Farzaneh, Scripta Mater., 57(2007) 937-940.

• [13]

Ø.Grong, L.Kolbeinsen, C.Van Der Eijk, and G.Tranell, ISIJ. Int., 46(2006) 824-831.

• [14]

M.Kiviö, L.Holappa, and T.Iung, Metall. Mater. Trans. B, 41(2010) 1194-1204.

• [15]

X.Z.Gao, S.F.Yang, J.S.Li, Y.D.Yang, K.Chattopadhyay, and A.Mclean, Metall. Mater. Trans. A, 47(2016) 461-470.

• [16]

X.Z.Gao, S.F.Yang, J.S.Li, H.Liao, W.Gao, and T.Wu, Metall. Mater. Trans. B, 47(2016) 1124-1136.

• [17]

H.Guo, S.F.Yang, J.S.Li, M.J.Zhao, Z.Y.Chen, X.L.Zhang, and J.K.Li, JOM, 70(2018) 1136-1142.

• [18]

S.-J.Zhuo, Y.-Q.Wang, X.-H.Wang, and H.-G.Lee, J Iron Steel Res Int., 17(2010) 10-16. Google Scholar

• [19]

X.B.Li, M.Yi, C.J.Liu, and M.F.Jiang, STEEL RES INT, 87(2016) 622-632.

• [20]

Y.Liu, X.L.Wan, G.Q.Lia, Y.Wang, W.Zheng and Y.H.Hou, SCI TECH-NOL WELD, 27(1996) 848-853. Google Scholar

• [21]

X.X.Deng, J.Min, and X.-H.Wang, Acta Metall. Sin.(Engl. Lett.), 25(2012) 241-248. Google Scholar

• [22]

B.L.Cai, and M.X.Jiang, REFRACT, 43(2009) 346-349. Google Scholar

• [23]

T.S.Zhang, C.J.Liu, J.Y.Qiu, X.B.Li, and M.F.Jiang, ISIJ. Int., 57(2017) 314-321.

• [24]

P.Shen, L.F.Zhang, H.Zhou, Y.Ren, and Y.Wang, Ceram. Int., 43(2017) 7674-7681.

• [25]

L.C.Zheng, A.Malfliet, P.Wollants, B.Blanpain, and M.Guo, Metall. Mater. Trans. B, 48(2017) 2447-2458.

• [26]

Y.Ueshima, S.Mizoguchi, T.Matsumiya, and H.Kajioka, Metall. Mater. Trans. B, 17(1986) 845-859.

• [27]

T.Yokoyama, Y.Ueshima, K.Sasai, Y.Mizukami, H.Kakimi and M.Kato, Tetsu-to-Hagané, 83(1997) 25-30. Google Scholar

• [28]

H.Ono, K.Morita, and N.Sano, Metall. Mater. Trans. B, 26(1995) 991-995. Google Scholar

• [29]

H.Ono, H.Fukagawa, K.Morita, and N.Sano, Metall. Mater. Trans. B, 24(2018) 43-51. Google Scholar

• [30]

K.Ogino, K.Nogi, and O.Yamase, Transactions ISIJ, 23(1983) 234-239.

Accepted: 2018-12-25

Published Online: 2019-05-11

Published in Print: 2019-02-25

Citation Information: High Temperature Materials and Processes, Volume 38, Issue 2019, Pages 576–581, ISSN (Online) 2191-0324, ISSN (Print) 0334-6455,

Export Citation


text:
# How could I match the surrounding traffics displayed with their radio communication

If I have a traffic display I could see the traffics in proximity of my aircraft and meanwhile I could listen to their voice communication. So how could I match the traffic shown in the display with the corresponding voice communication? My understanding is that if I have a ADS B in system and the other aircrafts have mode-s transponder, I could know their call sign thru the ADS-B data, is that right? But how about I just have a TCAS or I have the ADS-B in transponder but other aircrafts do not have a Mode-S transponder?

• IANAP, but shouldn't all radio communication start with <who I am> and <who I'm talking to> (maybe in the other order)? If you hear someone say N12345 on approach runway 17L, you should be able to correlate N12345 with the appropriately labeled blip on your traffic display, no? Oct 1 '19 at 17:57
• I could correlate N12345 to the traffic on my display who is indicated as approaching RW17L, but I can not be 100% sure, right? N12345 could be a aircraft without transponder, that is not shown on my traffic display or I have 2 traffics displayed as on the approach and I still can not tell which one is N12345, please correct me.
– VvV
Oct 1 '19 at 18:07

format: plain


text:
# Conjugation in fundamental group

Let X be a topological space, and let $x_0$ be a point of X. Show that if $\lambda_1$ and $\lambda_2$ in $\pi(X; x_0)$ have the same image under $\pi(X; x_0) \rightarrow [S^1;X]$, then $\lambda_1$ and $\lambda_2$ are conjugate. (Conjugate in the group sense).

I'm confused as to what the images look like in $[S^1; X]$

-
Hint: $\pi_1$ is also defined in terms of loops in $X$ — so what's the difference b/w $\pi_1(X)$ and $[S^1,X]$?.. –  Grigory M Nov 19 '11 at 18:34

I think this question is really of the following form: if $f_1,f_2: S^1 \to X$ represent elements $\alpha, \beta$ in $G=\pi_1(X,x_0)$, and $f_1,f_2$ are freely homotopic, then $\alpha, \beta$ are conjugate in the group $G$. Here freely homotopic means not respecting the base point.
So if $a$ is the base point of $S^1$, then $f_1(a)=f_2(a)=x_0$, but the homotopy determines an element $\gamma$ of $G$ represented by the path, say $k$, of the base point during the homotopy. Then $\gamma$ conjugates $\alpha$ to $\beta$ in $G$.
There are several ways to see this. One is to represent the homotopy as a square in which the bottom and top edges are given by $f_1,f_2$ and the vertical edges are given by $k$, since the square identifies to a cylinder to give a homotopy of maps of $S^1$. Because the square is convex, it determines a homotopy which gives the equation $\alpha \gamma= \gamma \beta$.


text:
# Yale shooting problem

The Yale shooting problem is a conundrum or scenario in formal situational logic on which early logical solutions to the frame problem fail. The name of this problem derives from its inventors, Steve Hanks and Drew McDermott, working at Yale University when they proposed it. In this scenario, Fred (later identified as a turkey) is initially alive and a gun is initially unloaded. Loading the gun, waiting for a moment, and then shooting the gun at Fred is expected to kill Fred. However, if inertia is formalized in logic by minimizing the changes in this situation, then it cannot be uniquely proved that Fred is dead after loading, waiting, and shooting. In one solution, Fred indeed dies; in another (also logically correct) solution, the gun becomes mysteriously unloaded and Fred survives.

Technically, this scenario is described by two fluents (a fluent is a condition that can change truth value over time): ${\displaystyle alive}$ and ${\displaystyle loaded}$. Initially, the first condition is true and the second is false. Then, the gun is loaded, some time passes, and the gun is fired. Such problems can be formalized in logic by considering four time points ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle 2}$, and ${\displaystyle 3}$, and turning every fluent such as ${\displaystyle alive}$ into a predicate ${\displaystyle alive(t)}$ depending on time. A direct formalization of the statement of the Yale shooting problem in logic is the following one:

${\displaystyle alive(0)}$
${\displaystyle \neg loaded(0)}$
${\displaystyle true\rightarrow loaded(1)}$
${\displaystyle loaded(2)\rightarrow \neg alive(3)}$

The first two formulae represent the initial state. The third formula formalizes the effect of loading the gun at time ${\displaystyle 0}$. The fourth formula formalizes the effect of shooting at Fred at time ${\displaystyle 2}$. This is a simplified formalization in which action names are neglected and the effects of actions are directly specified for the time points in which the actions are executed. See situation calculus for details.

The formulae above, while being direct formalizations of the known facts, do not suffice to correctly characterize the domain. Indeed, ${\displaystyle \neg alive(1)}$ is consistent with all these formulae, although there is no reason to believe that Fred dies before the gun has been shot. The problem is that the formulae above only include the effects of actions, but do not specify that all fluents not changed by the actions remain the same. In other words, a formula ${\displaystyle alive(0)\equiv alive(1)}$ must be added to formalize the implicit assumption that loading the gun only changes the value of ${\displaystyle loaded}$ and not the value of ${\displaystyle alive}$. The necessity of a large number of formulae stating the obvious fact that conditions do not change unless an action changes them is known as the frame problem.

An early solution to the frame problem was based on minimizing the changes. In other words, the scenario is formalized by the formulae above (that specify only the effects of actions) and by the assumption that the changes in the fluents over time are as minimal as possible. The rationale is that the formulae above enforce all effect of actions to take place, while minimization should restrict the changes to exactly those due to the actions.

In the Yale shooting scenario, one possible evaluation of the fluents in which the changes are minimized is the following one.

 ${\displaystyle alive(0)}$ ${\displaystyle alive(1)}$ ${\displaystyle alive(2)}$ ${\displaystyle \neg alive(3)}$ ${\displaystyle \neg loaded(0)}$ ${\displaystyle loaded(1)}$ ${\displaystyle loaded(2)}$ ${\displaystyle loaded(3)}$

This is the expected solution. It contains two fluent changes: ${\displaystyle loaded}$ becomes true at time 1 and ${\displaystyle alive}$ becomes false at time 3. The following evaluation also satisfies all formulae above.

 ${\displaystyle alive(0)}$ ${\displaystyle alive(1)}$ ${\displaystyle alive(2)}$ ${\displaystyle alive(3)}$ ${\displaystyle \neg loaded(0)}$ ${\displaystyle loaded(1)}$ ${\displaystyle \neg loaded(2)}$ ${\displaystyle \neg loaded(3)}$

In this evaluation, there are still two changes only: ${\displaystyle loaded}$ becomes true at time 1 and false at time 2. As a result, this evaluation is considered a valid description of the evolution of the state, although there is no valid reason to explain ${\displaystyle loaded}$ being false at time 2. The fact that minimization of changes leads to wrong solution is the motivation for the introduction of the Yale shooting problem.

While the Yale shooting problem has been considered a severe obstacle to the use of logic for formalizing dynamical scenarios, solutions to it are known since the late 1980s. One solution involves the use of predicate completion in the specification of actions: according to this solution, the fact that shooting causes Fred to die is formalized by the preconditions: alive and loaded, and the effect is that alive changes value (since alive was true before, this corresponds to alive becoming false). By turning this implication into an if and only if statement, the effects of shooting are correctly formalized. (Predicate completion is more complicated when there is more than one implication involved.)

A solution proposed by Erik Sandewall was to include a new condition of occlusion, which formalizes the “permission to change” for a fluent. The effect of an action that might change a fluent is therefore that the fluent has the new value, and that the occlusion is made (temporarily) true. What is minimized is not the set of changes, but the set of occlusions being true. Another constraint specifying that no fluent changes unless occlusion is true completes this solution.

The Yale shooting scenario is also correctly formalized by the Reiter version of the situation calculus, the fluent calculus, and the action description languages.

In 2005, the 1985 paper in which the Yale shooting scenario was first described received the AAAI Classic Paper award. In spite of being a solved problem, that example is still sometimes mentioned in recent research papers, where it is used as an illustrative example (e.g., for explaining the syntax of a new logic for reasoning about actions), rather than being presented as a problem.


text:
Opened 6 years ago

Closed 6 years ago

# TestManager is not installable on Trac 0.12.2

Reported by: Owned by: A.Stroppel@… Roberto Longobardi high TestManagerForTracPlugin blocker trac 0.12 TestManagerPlugin 0.12

### Description

When trying to install the TestManagerForTracPlugin, the installation hangs in the installation of the testmanager_plugin. I tried to go back in versions to install and found out that release 1.3.11 is the last one working.

The failure I get is, that trac always requests to upgrade the backend. But even after upgrading using the trac-admin command this error isn't solved. So I am unable to start my trac again.

Greetings Andreas

### comment:1 Changed 6 years ago by Roberto Longobardi

Hi Andreas, actually this is strange, since you are the first to report this issue. Also, the plugin installs correctly in my 0.12.2 environment.

Please, could you turn debug on in your trac and attach the errors you get during the upgrade?

Ciao, Roberto

### comment:3 Changed 6 years ago by anonymous

Hi there,

the installation is no upgrade its a fresh install. We also where a bit suprised, that no one else has this failure as we tracked down this behaviour till 1.3.12 of you're plugin. But we also recognized that all your bugs tracked since 1.3.12 are for trac 0.11 not for 0.12 so perhaps something is anyway strange there. Let's see...

So, hopefully here are all information you requested. If it's to less or if you miss something don't hesitate to give me a hint.

PreRequisits before installing your addon: Trac 12.2 installed completely from scratch TracXMLRPC 1.1.2-r9913

Installation procedure:

1. installed TracGenericClass-1.0.4-py2.6.egg

upgrade procedure it tells everything is fine.

The system trac is installed is: vmware maschine with debian (kernel 2.6.32-5-amd64 think it is a lenny) installed Python 2.6.6 Apache 2.2.16

According to the Logfiles Trac is missing some Libraries like: Pygments>=0.6 docutils>=0.3 SilverCity>=0.9.4 textile>=2.0

But as I couldn't find any documentation saying that are prerequisites I thought they are optional.

1. On installing Generic Class:
Mar 17 12:47:04 ## Trac[api] INFO: Synchronized '' repository in 0.01 seconds
Mar 17 12:47:04 ## Trac[web_ui] INFO: Installing plugin TracGenericClass-1.0.4-py2.6.egg
Mar 17 12:47:04 ## Trac[web_ui] INFO: Plugin TracGenericClass-1.0.4-py2.6.egg installed to /var/lib/trac/plugins/TracGenericClass-1.0.4-py2.6.egg
Mar 17 12:47:04 ## Trac[env] INFO: Reloading environment due to configuration change
Mar 17 12:47:04 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:47:04 ## Trac[env] WARNING: base_url option not set in configuration, generated links may be incorrect
Mar 17 12:47:04 ## Trac[api] INFO: Synchronized '' repository in 0.01 seconds
Mar 17 12:47:05 ## ï»¿<12>Trac[chrome] WARNING: File your_project_logo.png not found in any of ['/var/lib/trac/htdocs']

1. On installing Generic Workflow:
Mar 17 12:49:26 ## Trac[env] INFO: Reloading environment due to configuration change
Mar 17 12:49:26 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:49:26 ## Trac[env] WARNING: base_url option not set in configuration, generated links may be incorrect
Mar 17 12:49:26 ## Trac[api] INFO: Synchronized '' repository in 0.01 seconds
Mar 17 12:49:26 ## Trac[web_ui] INFO: Installing plugin TracGenericWorkflow-1.0.2-py2.6.egg
Mar 17 12:49:26 ## Trac[web_ui] INFO: Plugin TracGenericWorkflow-1.0.2-py2.6.egg installed to /var/lib/trac/plugins/TracGenericWorkflow-1.0.2-py2.6.egg
Mar 17 12:49:26 ## Trac[env] INFO: Reloading environment due to configuration change
Mar 17 12:49:26 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:49:26 ## Trac[env] WARNING: Component <tracgenericworkflow.model.GenericWorkflowModelProvider object at 0x7fad54465510> requires environment upgrade

Mar 17 12:50:47 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:50:47 ## Trac[env] WARNING: Component <tracgenericworkflow.model.GenericWorkflowModelProvider object at 0x33bf110> requires environment upgrade
Mar 17 12:50:47 ## Trac[env] INFO: tracgenericworkflow.model.GenericWorkflowModelProvider upgrading...

3.2 On refreshing Trac after upgrade:

Mar 17 12:52:46 ## Trac[env] INFO: Reloading environment due to configuration change
Mar 17 12:52:46 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:52:46 ## Trac[env] WARNING: base_url option not set in configuration, generated links may be incorrect
Mar 17 12:52:46 ## Trac[api] INFO: Synchronized '' repository in 0.01 seconds
Mar 17 12:52:47 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:52:47 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:52:47 ## Trac[env] WARNING: base_url option not set in configuration, generated links may be incorrect
Mar 17 12:52:47 ## Trac[env] WARNING: base_url option not set in configuration, generated links may be incorrect
Mar 17 12:52:47 ## ï»¿<12>Trac[chrome] WARNING: File your_project_logo.png not found in any of ['/var/lib/trac/htdocs']
Mar 17 12:52:47 ## ï»¿<12>Trac[chrome] WARNING: File your_project_logo.png not found in any of ['/var/lib/trac/htdocs']

1. on installing TestManager:
Mar 17 12:53:35 ## Trac[api] INFO: Synchronized '' repository in 0.01 seconds
Mar 17 12:53:35 ## Trac[web_ui] INFO: Installing plugin TestManager-1.4.4-py2.6.egg
Mar 17 12:53:35 ## Trac[web_ui] INFO: Plugin TestManager-1.4.4-py2.6.egg installed to /var/lib/trac/plugins/TestManager-1.4.4-py2.6.egg
Mar 17 12:53:35 ## Trac[env] INFO: Reloading environment due to configuration change
Mar 17 12:53:35 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:53:35 ## Trac[env] WARNING: Component <testmanager.model.TestManagerModelProvider object at 0x7fad53d18710> requires environment upgrade

3.1 On upgrading after TestManager install:

Mar 17 12:54:23 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:54:24 ## Trac[env] WARNING: Component <testmanager.model.TestManagerModelProvider object at 0x1c7d110> requires environment upgrade
Mar 17 12:54:24 ## Trac[env] INFO: testmanager.model.TestManagerModelProvider upgrading...

Mar 17 12:54:51 ## Trac[env] INFO: Reloading environment due to configuration change
Mar 17 12:54:51 ## Trac[env] INFO: Reloading environment due to configuration change
Mar 17 12:54:51 ## Trac[env] INFO: -------------------------------- environment startup [Trac 0.12.2] --------------------------------
Mar 17 12:54:51 ## Trac[env] WARNING: Component <trac.ticket.default_workflow.ConfigurableTicketWorkflow object at 0x7fad54218c90> requires environment upgrade

### comment:4 Changed 6 years ago by anonymous

Ok,

should read the manual for the trac wiki. The format got lost in my last Response. Sorry on that. If I have to format it better give me an information. But i can't change the last one as it was written anonymous.. :(

### comment:5 Changed 6 years ago by anonymous

OK, installed the missing tools except SilverCity. Nothing changed...

Greetings Andreas

### comment:6 Changed 6 years ago by anonymous

grml sorry.. missed the used Database: we use the sqlite DB.

### comment:7 Changed 6 years ago by Roberto Longobardi

Hi Andreas, from the log you attached it looks like the ticket workflow engine (not test manager) keeps asking for upgrade in the end:

Mar 17 12:54:51 ## Trac[env] WARNING: Component <trac.ticket.default_workflow.ConfigurableTicketWorkflow? object at 0x7fad54218c90> requires environment upgrade

This may be a side effect of the test manager installation??? Let's try to understand why.

I don't see anything in the your last log file about the test manager plugins starting... Did you remove the section from the log?

• attach (as a file to this ticket) the complete trac log file after a full restart and after issuing the database upgrade command
• attach your trac.ini file (there may be conflicts between test manager workflow and ticket workflow??)

BTW, I too don't have silvercity and the other mising plugins in place, and everything still works fine.

Also, I am aware of people using test manager with 0.12.1 successfully. So let's track down your issue! :-)

Ciao, Roberto

### comment:8 Changed 6 years ago by anonymous

Hi Roberto,

"Also, I am aware of people using test manager with 0.12.1 successfully. So let's track down your issue! :-) "

-> Just to be correct .. we use 0.12.2

"Did you remove the section from the log?"

-> No definitly not but this time i attach the hole log File at once

Hopefully we find the reason for this. As I really like your tool. Just for another question, is it possible to version the Testcases themself? As the testcases change for other releases this would be really cool... Couldn't find anything on this yet.

Greetings Andreas

### comment:9 Changed 6 years ago by Roberto Longobardi

Hi Andreas, I looked at the log files and it looks like the test manager plugin database upgrade was successful... No errors and the next trac restart does not fail.

I noticed that sometimes the errors will only be shown when, after the next restart, you try to access any trac web page. So please, could you try to open the trac site with your browser and attach the log file again?

The trac.ini file seems correct...

Yes, I know you are on 0.12.2, but as I said I tried with that without any problem...

So, summarizing, there is no error in your log file or ini file, and I don't understand what's going wrong...

Please, could you try to reproduce the condition when trac keeps asking for an upgrade and attach the log file?

Ciao, Roberto

### comment:10 Changed 6 years ago by anonymous

Reproduction is no problem as this always happens when I try to install.

In the attached File Trac.ini.zip you can find the requested log. I refreshed the Browser for 3-4 Times always after doing an upgrade and before doing an upgrade.

Perhaps another thing that can help. When I try to upgrade not doing a full install, it seems that everything worked. The installation runs full. But at the end there still is the old version listed. This behaviour stays till i restart my apache ... then I again run in the admin upgrade failure.

So perhaps something is wrong with some cashing of Apache. Just to clearify this I did an installation keeping apache restarting after every try with the same results...

Greetings Andreas

### comment:11 Changed 6 years ago by Roberto Longobardi

Hi Andreas, I spent some time setting up the apache with wsgi environment and used the prolog you attached here as my project.

Then installed the generic class and workflow plugins, did the database upgrade command and finally installed the test manager plugin, again with a database upgrade command.

Everything works fine.

Let me give you some info about my environment:

I'm running Ubuntu and I have Trac 0.12.2 installed inside a virtual python environment, so I can have 0.11, 0.12.1 and 0.12.2 coexisting in my machine.

I usually run everything with my user, never with root privileges. Anyway, in the new Apache with mod wsgi environment I had to run the "trac-admin ... upgrade" commands as root, otherwise they kept failing and scratched my trac.ini file. After that, the ConfigurableTicketWorkflow plugin kept asking for an upgrade. This was just because, with an empty trac.ini file, that plugin thinks it has to do an upgrade.

Ciao, Roberto

### comment:12 Changed 6 years ago by anonymous

Hi Roberto,

for this test installation we installed the whole trac and your plugin completely under root. So this should work for sure shouldn't it ?

The already attached trac.ini was the trac.ini after installation of all *.egg files. So you could use that one.

I checked again and can tell now we use a debian squeeze installation. with this wsgi installation and python without virtual ;)

So as you found out, there could be a problem with user rights, but I'm not sure how this can solve to us as we have done all with root.

The only thing i can assume is, that we switched the whole directory after installation to the webserver user. But we did the trac-admin with root.

Im getting slowly confused ;)

If I understood right, it seems we have a unvalid trac.ini. So if you attach the trac.ini after your installation it will run for us, but it wont give you hints about the problem.

In the next step we will try to setup a new vmware session with a new linux and try the whole installation from scratch, just to see if something with the environment got screwed up...

Greetings Andreas

### comment:13 Changed 6 years ago by Roberto Longobardi

Hi Andreas, I am confused too...

Looking at the log file, it looks like you have installed TracXMLRPC under: /usr/local/lib/python2.6/dist-packages/TracXMLRPC-1.1.2_r9913-py2.6.egg

and TestManager under your project environment: /var/lib/trac/prolog/plugins/TestManager-1.4.4-py2.6.egg

One thing that comes into my mind is to try and install TestManager under the root python dir.

Looking at the trac.ini file after the installation it looks like the Test Manager part is missing. You should find the following sections:

{{ [test-outcomes] default = TO_BE_TESTED green.successful = Successful red.failed = Failed yellow.to_be_tested = Untested

[ticket-custom] planid = text planid.label = Test Plan testcaseid = text testcaseid.label = Test Case }}}

The part related to ConfigurableTicketWorkflow instead is there:

[ticket-workflow]
accept = new,assigned,accepted,reopened -> accepted
accept.operations = set_owner_to_self
accept.permissions = TICKET_MODIFY
leave = * -> *
leave.default = 1
leave.operations = leave_status
reassign = new,assigned,accepted,reopened -> assigned
reassign.operations = set_owner
reassign.permissions = TICKET_MODIFY
reopen = closed -> reopened
reopen.operations = del_resolution
reopen.permissions = TICKET_CREATE
resolve = new,assigned,accepted,reopened -> closed
resolve.operations = set_resolution
resolve.permissions = TICKET_MODIFY

so I'm wondering why this plugin keeps asking for an upgrade (which it does when it doesn't find this section in the trac.ini file).

I really think there is something wrong with your apache/trac installation that's preventing the upgrade to be successful. Unfortunately I'm not very expert with that...

I would suggest you to try to use virtualenv to install trac and the plugin, and run tracd as the server. When that works, you may try to switch to Apache.

I did it (with some exceptions) and came out with a perfectly working apache+wsgi+trac+test manager environment.

If you need, as soon as I come home tonight I can try to recap all the commands and configurations I made and write them down here.

Let me know. Ciao, Roberto

### comment:14 Changed 6 years ago by Roberto Longobardi

[test-outcomes]
default = TO_BE_TESTED
green.successful = Successful
red.failed = Failed
yellow.to_be_tested = Untested

[ticket-custom]
planid = text
planid.label = Test Plan
testcaseid = text
testcaseid.label = Test Case

### Changed 6 years ago by Roberto Longobardi

My working configuration files

### comment:15 Changed 6 years ago by Roberto Longobardi

Hi Andreas, I've added an attachment to this ticket with some of my working configuration files.

Please, note that Trac has been installed using virtualenv, under /home/roberto/trac0122. You find it referenced in wsgi.conf which resides in /etc/apache2/mods-available and is linked under mods-enabled.

The sample project environment is under /home/roberto/projects/prova_012_2_lang_01. You find it referenced in several places.

The apache mod_wsgi configuration file for trac is found under the project environment, specifically in /home/roberto/projects/prova_012_2_lang_01/apache/wsgi_trac_conf.wsgi. You find it referenced in httpd.conf.

I didn't touch apache2.conf at all.

Note that I had to manually create the /home/roberto/projects/prova_012_2_lang_01/eggs directory (the PYTHON_EGG_CACHE), and give it 777 permissions, otherwise I got an error.

Generally speaking, I didn't quite paid attention to the security stuff. So I simply gave 777 to all the trac project environment tree, to let the apache user access it.

Hope this helps. Ciao, Roberto

### comment:16 Changed 6 years ago by anonymous

Hello Roberto,

thanks for your help till now. I will try to setup a new system. Perhaps this solves the error.

What looks the strangest to me is the fact, that I can install 1.3.11 Version but no version since 1.4.x. I also tried to give 777 rights to all my files it didn't worked.

even copying the trac.ini File of my 1.3.11 installation in the 1.4.11 installation didn't worked. It also asks for an upgrade and again hangs after that.

Would have been interesting whats the reason for this ...

Greetings Andreas

### comment:17 Changed 6 years ago by stefan.voelkel@…

Hi,

I narrowed it down to version 12.1 of trac. I can install TestManager on Debian Squeeze with Trac 12.0.

Trac 12.1, 12.2, 13dev does not work.

HTH

Stefan

### comment:18 Changed 6 years ago by Roberto Longobardi

Hi Stefan, I can run the plugin with no flaws on Ubuntu 10.10 and Trac 0.12.2, with apache and mod_wsgi, and with the configuration I attached to this ticket.

So the problem seems related to other distributions.

In order to reproduce it I installed a virtual machine with Debian Squeeze last night (literally :-)), apache and mod_wsgi, but have some problems configuring the security (I'm, no apache expert I'm afraid...).

I'm trying basic authentication, to keep it simple, but I keep getting "unauthorized" errors on my /trac and /trac/login pages. I followed the instructions on TracModWSGI, but with no luck.

Would you help me by attaching a set of config files for apache (i.e. apache2.conf, httpd.conf, mod_wsgi.conf, ...) that work on a clean Debian, even without any security in place?

Thanks, ciao.

Roberto

### comment:19 Changed 6 years ago by stefan.voelkel@…

The "interesting" appache part:

        WSGIScriptAlias /trac /var/lib/trac/foo/foo.wsgi
<Directory /var/lib/trac/foo/apache>
WSGIApplicationGroup %{GLOBAL}
Order deny,allow
Allow from all
</Directory>
<Location /trac>
AuthType Basic
AuthName "trac"
AuthUserFile /var/lib/trac/foo/conf/passwd
Require valid-user
</Location>

foo.wsgi

import os

os.environ['TRAC_ENV'] = '/var/lib/trac/foo'
os.environ['PYTHON_EGG_CACHE'] = '/var/lib/trac/foo/eggs'

import trac.web.main
application = trac.web.main.dispatch_request

wsgi.conf is unchanged, but I'll attach it.

However I don't think wsgi is needed, "normal" cgi should also reproduce the problem.

### comment:20 Changed 6 years ago by Roberto Longobardi

Actually I have a working environment with TestManager 1.4.4 in Debian Squeeze.

Take a look at the attached screenshots.

Installation or database did not give me any error...

Let me recap what I did, everything as root, on a freshly installed Debian:

1. Compiled and installed it:
tar xvzf setuptools-0.6c11.tar.gz
cd setuptools-0.6c11/
python setup.py install

1. Installed Trac 0.12.2 using the now available easy_install:
easy_install Trac

1. Created needed directories to host the foo project:
mkdir -p /var/lib/trac

1. Created a foo trac project environment:
trac-admin /var/lib/trac/foo initenv

1. Created a password file for apache authentication:
htpasswd -c /var/lib/trac/foo/conf/passwd admin
htpasswd /var/lib/trac/foo/conf/passwd roberto

trac-admin /var/lib/trac/foo permission add anonymous TRAC_ADMIN

1. Run trac through tracd just to see everything worked:
tracd --port 8000 /var/lib/trac/foo

1. Set trace level to DEBUG in trac, and log to file, using the admin panel.
1. Configured apache and wsgi using exactly the info and paths Stefan provided.
1. Granted everyone 777 on /var/lib/trac:
chmod -R 777 /var/lib/trac

1. Started apache:
/etc/init.d/apache2 restart

1. Verified trac was up and running, with basic authentication working, using the browser.
1. Downloaded egg files for the TestManager plugin, 1.4.4, from sourceforge, and extracted archive.
1. Opened browser to the foo trac project, on the admin panel, and installed TracGenericClass plugin from the egg file.
1. Installed TracGenericWorkflow plugin the same way. This asks for database upgrade.
1. Opened shell as root and fired the command on screen:
trac-admin /var/lib/trac/foo upgrade

1. Restarted apache, just to be sure cache was updated:
/etc/init.d/apache2 restart

1. Refreshed browser. The trac admin page shows correctly.
1. Installed TestManager plugin the same way. This asks for another database upgrade.
1. Opened shell as root and fired the command on screen:
trac-admin /var/lib/trac/foo upgrade

1. Restarted apache. I think this time is required:
/etc/init.d/apache2 restart

1. Refreshed browser. The trac admin page shows correctly.
1. Went to test manager home page and created a test catalog. See screenshot.

I really don't understand what went wrong in your environments.

Please, double check the steps above with what you did so we can find what's different.

Hope this helps. Ciao, Roberto

### Changed 6 years ago by Roberto Longobardi

Admin page after plugins installed on Debian

### Changed 6 years ago by Roberto Longobardi

A working test catalog on Debian

### comment:21 Changed 6 years ago by Roberto Longobardi

Hi all, did you have any chance to verify the environment setup steps above?

Ciao, Roberto

### comment:22 Changed 6 years ago by Roberto Longobardi

Notice that I didn't install XmlRpc Plugin.

### comment:23 Changed 6 years ago by Roberto Longobardi

Resolution: → worksforme new → closed

Please, let me know if you keep having problems.

### comment:24 Changed 6 years ago by Russ Tyndall

Some users of my plugin are experiencing similar problems, that I also could not trac down in my plugin (TimingAndEstimationPlugin). Please see http://trac-hacks.org/ticket/8575#comment:19 for more information. If I can trac down what the problem is and get it reproduceable I will report this upstream

### comment:25 Changed 6 years ago by Russ Tyndall

My bug ended up being bad permissions on the config file, which manifested as need to upgrade in apache, but sudo trac-admin ... was working (because root had access to the conf, but apache didnt).

### comment:26 Changed 6 years ago by Roberto Longobardi

Thanks a lot Bobby for this info.

I just had a similar ticket closed that was tracked down to the same problem: write permission needed on the trac.ini file for the PostgreSQL database user.

Thanks, ciao! Roberto

### comment:27 Changed 6 years ago by Russ Tyndall

This problem has been addressed in the version 13 dev branches of trac.

Just for other's reference:

### Modify Ticket

Change Properties


text:
# Airy in the library

November 20, 2015

Airy functions, named after the British astronomer and mathematician George Biddell Airy, are solutions of the following second-order ODE:

$$f''(x) = x f(x).$$ The Airy equation is the prototypical ODE with a turning point. Consider the following ODEs and their respective solutions:

$$f''(x) = +f(x), \quad f(x) = C_1 \exp(x) + C_2 \exp(-x)$$ $$f''(x) = -f(x), \quad f(x) = C_1 \sin(x) + C_2 \cos(x)$$

When $x > 0$, the Airy equation resembles the first equation: the solutions either increase or decrease exponentially. When $x < 0$, the Airy equation resembles the second equation: the solutions oscillate like sines and cosines.

The general solution of the Airy equation is $C_1 \operatorname{Ai}(x) + C_2 \operatorname{Bi}(x)$, where Ai and Bi are two special solutions which have been defined so that Ai is decreasing and Bi is increasing to the right of the turning point at $x = 0$.

Airy functions are useful in asymptotic analysis of differential equations, and they show up in a huge number of applications in physics. One of the textbook examples in quantum mechanics is the one-dimensional stationary Schrödinger equation for a particle in a linear potential, $$\left[ \frac{-\hbar^2}{2\mu}\nabla^2 + (V(x) - E) \right] \Psi(x) = 0, \quad V(x) = C x,$$ which is equivalent to the Airy equation after a change of variables.

## Implementation in Arb

Airy functions can be expressed in terms of Bessel functions or confluent hypergeometric functions of orders $n \pm 1/3$. In particular, $$\operatorname{Ai}(z) = \frac{1}{3^{2/3} \Gamma(2/3)} {}_0F_1\left(\frac{2}{3}, \frac{z^3}{9}\right) - \frac{z}{3^{1/3} \Gamma(1/3)} {}_0F_1\left(\frac{4}{3}, \frac{z^3}{9}\right)$$ $$\operatorname{Bi}(z) = \frac{1}{3^{1/6} \Gamma(2/3)} {}_0F_1\left(\frac{2}{3}, \frac{z^3}{9}\right) + \frac{3^{1/6} z}{\Gamma(1/3)} {}_0F_1\left(\frac{4}{3}, \frac{z^3}{9}\right).$$

The Airy functions could have been implemented rather easily by wrapping the pre-existing Bessel functions or confluent hypergeometric functions in Arb, but I decided to do a more elaborate implementation from scratch instead (main commit).

Why? First of all, the pre-existing Bessel and hypergeometric code is less than optimal for order $n \pm 1/3$ (fractions with power-of-two denominators are more efficient due to being exact). Even if I were to fix this deficiency, going via other special functions would still involve a lot of redundant computation. I also wanted to make the Airy functions numerically stable everywhere, meaning that the error bounds for the output should be close to the best possible, given a nonzero error bound for the input. This is currently not the case for Bessel functions in Arb. Obviously, I want to make the Bessel functions more numerically stable too, but that is a much harder project for the future!

The implementation of Airy functions in Arb (acb_hypgeom_airy and its helper functions) comprises some 2000 lines of code including unit tests and documentation, and has the following features:

• The input $z$ is a complex interval. The code supports arbitrary precision and gives rigorous error bounds (obviously).
• Any combination of the four functions $\operatorname{Ai}(z), \operatorname{Ai}'(z), \operatorname{Bi}(z), \operatorname{Bi}'(z)$ can be computed simultaneously (like sine and cosine, they are often used together, and this is faster than performing 2-4 independent function evaluations).
• For small and exact $z$, the convergent ${}_0F_1$ series are used. The working precision is automatically increased to compensate for catastrophic cancellation.
• For small and inexact $z$, the functions are evaluated at the midpoint of $z$, and accurate propagated error bounds are computed using derivative bounds obtained from asymptotic expansions.
• For large $z$, asymptotic expansions are used directly. This is automatically numerically stable.
• Hardware double-precision arithmetic is used to quickly determine whether asymptotic expansions can be used, and to compute tight estimates of the number of terms to use and the working precision needed to overcome cancellation. This is a heuristic step, and error bounds are subsequently computed rigorously using interval arithmetic and directed rounding.
• Both the convergent and asymptotic series are evaluated using an efficient rectangular splitting strategy to reduce the number of costly multiplications.

Note that while only the zeroth and first order derivatives are computed, both Ai and Bi satisfy $$f^{(2)}(z) = z f(z)$$ $$f^{(n+3)}(z) = z f^{(n+1)}(z) + (n+1) f^{(n)}(z),$$ so computing the higher derivatives is a simple exercise for the user. I might add convenience functions later for evaluating Airy functions of power series.

## Asymptotic expansions

I will elaborate on how asymptotic functions are used, because this bit was somewhat painful to work out in detail. The math is simple; the difficulty was to get the error bounds right everywhere, including corner cases where the input is an interval straddling more than one region, and implementing everything in verbose C code with redundant steps optimized out.

First, recall that for a given tolerance $2^{-p}$, asymptotic expansions can be used only when $|z|$ is sufficiently large. For given $z$ and $p$, how do we find out whether asymptotic expansions give sufficient accuracy, and how many terms to use? If we denote the terms in the asymptotic expansion by $t(n)$, the easiest way is to simply estimate $\log_2 |t(0)|, \log_2 |t(1)|, \ldots$. We can proceed to use the asymptotic series when we find an $n$ such that $\log_2 |t(n)| < -p$. If we run into an $n$ such that $\log_2 |t(n)| > \log_2 |t(n-1)|$, the asymptotic series will not give sufficient accuracy, so we abort and use a convergent series instead. (This strategy is too simplistic for asymptotic series in general, but it works here.) This initial "parameter selection stage" can use cheap hardware arithmetic, as rigorous error bounds will be computed later.

I used the bounds derived by Frank Olver and presented in his chapter on Airy functions in the DLMF. The starting point is the asymptotic expansion for $\operatorname{Ai}(z)$ in the direction $z \to +\infty$, which actually is valid as $|z| \to \infty$ along any complex ray other than the negative half of the real line. With $\zeta = (2/3) z^{3/2}$, we have $$\operatorname{Ai}(z) = \frac{e^{-\zeta}}{2 \sqrt{\pi} z^{1/4}} \left[S_n(\zeta) + R_n(z)\right]$$ where $$S_n(\zeta) = \sum_{k=0}^{n-1} (-1)^k \frac{u(k)}{\zeta^k}, \quad u(k) = \frac{(1/6)_k (5/6)_k}{2^k k!}.$$

Olver gives an explicit bound for the error term $R_n(z)$. This bound deteriorates with increasing $\arg(z)$, as I have indicated in the figure below on the left. We get very good bounds for $|\arg(z)| < \pi / 3$ (green), just slightly worse bounds for $\pi / 3 < |\arg(z)| < 2 \pi / 3$ (yellow), worse but still usable bounds for $2 \pi / 3 < |\arg(z)| \ll \pi$ (orange), and near $|\arg(z)| = \pi$, the bounds blow up (red). We want to use this asymptotic expansion in the green sector if possible, and in the yellow sector otherwise. The orange sector can be used if there are no other options, and in that case we should try to stay close to the transition line between the yellow and orange sectors.

Left: quality of asymptotic expansion for $\operatorname{Ai}(z)$. Right: quality of asymptotic expansions for $\operatorname{Ai}(z), \operatorname{Bi}(z)$ using connection formulas.

Now the idea, as suggested by Olver, is to derive asymptotic expansions for other cases using connection formulas. For $z$ in the left half-plane, we can use

$$\operatorname{Ai}(z) = e^{+\pi i/3} \operatorname{Ai}(z_1) + e^{-\pi i/3} \operatorname{Ai}(z_2)$$ $$\operatorname{Bi}(z) = e^{-\pi i/6} \operatorname{Ai}(z_1) + e^{+\pi i/6} \operatorname{Ai}(z_2)$$ where $z_1 = -z e^{+\pi i/3}$ and $z_2 = -z e^{-\pi i/3}$. These connection formulas rotate the argument by one-third of a turn. Taking the asymptotic expansions of both the Airy functions on the right hand side, and combining terms, we get an expansion whose overall quality is the worse of the two. This is indicated in the picture above to the right. Explicitly, $$\operatorname{Ai}(z) = A_1 [S_n(i \zeta) + R_n(z_1)] + A_2 [S_n(-i \zeta) + R_n(z_2)]$$ $$\operatorname{Bi}(z) = A_3 [S_n(i \zeta) + R_n(z_1)] + A_4 [S_n(-i \zeta) + R_n(z_2)]$$ where $\zeta = (2/3) (-z)^{3/2}$ and $$A_1 = \frac{\exp(-i (\zeta - \pi/4))}{2 \sqrt{\pi} (-z)^{1/4}}, \quad A_2 = \frac{\exp(+i (\zeta - \pi/4))}{2 \sqrt{\pi} (-z)^{1/4}}, \quad A_3 = -i A_1, \quad A_4 = +i A_2.$$ Note that, although the connection formulas are valid for all $z$, the combined asymptotic expansion is only valid for $|\arg(-z)| < 2 \pi / 3$ (due to the branch cuts of the prefactor).

As a special case, looking at the negative half real axis in the picture above to the right, $\operatorname{Ai}(x)$ and $\operatorname{Bi}(x)$ with $x < 0$ become linear combinations of $\operatorname{Ai}(-x e^{\pm \pi i/3})$, lying on the transition lines between the yellow and green regions in the picture on the left.

The remaining case to handle is for Bi in the right half plane. Here we use the connection formulas $$\operatorname{Bi}(z) = -i (2 \omega^{+1} \operatorname{Ai}(z \omega^{-2}) - \operatorname{Ai}(z))$$ $$\operatorname{Bi}(z) = +i (2 \omega^{-1} \operatorname{Ai}(z \omega^{+2}) - \operatorname{Ai}(z))$$ where $\omega = \exp(\pi i/3)$. Combining roots of unity gives $$\operatorname{Bi}(z) = \frac{1}{2 \sqrt{\pi} z^{1/4}} [2X + iY]$$ $$\operatorname{Bi}(z) = \frac{1}{2 \sqrt{\pi} z^{1/4}} [2X - iY]$$ $$\zeta = (2/3) z^{3/2}, \quad X = \exp(+\zeta) [S_n(-\zeta) + R_n(z \omega^{\mp 2})], \quad Y = \exp(-\zeta) [S_n(\zeta) + R_n(z)]$$ where the upper formula is valid for $-\pi/3 < \arg(z) < \pi$ and the lower formula is valid for $-\pi < \arg(z) < \pi/3$, as illustrated in the following picture. We therefore use the upper formula when the midpoint of the complex interval $z$ lies in the upper half plane and the lower formula when the midpoint lies in the lower half plane (exactly on the real line, the choice is arbitrary).

Quality of asymptotic expansions for Bi in the right half plane.

Note that, in all cases, we we only need to evaluate $S_n(\zeta)$ and $S_n(-\zeta)$ with the same $\zeta$ to compute both Ai and Bi.

The formulas can be rearranged using trigonometric prefactors instead of exponentials. This makes everything real for negative real numbers, whereas the current formulas use alternating real and imaginary numbers there. Error bounds can also be simplified for purely real input: when the series are real and alternating, the error term is always bounded by the first omitted term. I might implement these improvements in the future.

## Benchmarking

For real arguments, we can compare performance with the mpfr_ai function in MPFR and airyai in mpmath. At 64-bit precision, Arb computes $\operatorname{Ai}(x)$ in 10-20 microseconds. This is about twice as fast as MPFR when $x$ is small. When $x$ grows larger, MPFR becomes progressively worse since it does not use asymptotic expansions. The plot below clearly shows the two peaks in running time where Arb switches to asymptotic expansions.

Time to compute $\operatorname{Ai}(x)$ at 64-bit precision.

Although mpmath uses asymptotic expansions and thus holds up decently for large arguments, it is much slower overall. The following plot shows, zoomed out, how many times faster Arb is compared to both MPFR and mpmath:

Relative to compute $\operatorname{Ai}(x)$ at 64-bit precision.

At 3333-bit precision (approximately 1000 digits), Arb computes $\operatorname{Ai}(x)$ in 2-5 milliseconds. This is again consistently faster than both MPFR and mpmath. The algorithm selection in mpmath is evidently very poorly tuned at high precision, slowing down so much that it goes off the scale in the following picture for $4 < x < 145$. Interestingly, though, mpmath is almost as fast as Arb for very large positive $x$ at this precision.

Time to compute $\operatorname{Ai}(x)$ at 3333-bit precision.

## Complex arguments

Complex arguments are uniformly 2-3 times slower than real arguments at the same precision. The following 512 × 512 pixel domain colored plots of $\operatorname{Ai}(z)$ (left) and $\operatorname{Bi}(z)$ (right) for $z \in [-10,10] + [-10,10]i$ take 4.5 seconds to render, using a precision of 32 bits.

## Airy function zeros

The Airy functions have an infinite sequence of real zeros $\operatorname{Ai}(a_n) = 0$, $\operatorname{Ai}'(a'_n) = 0$, $\operatorname{Bi}(b_n) = 0$, $\operatorname{Bi}'(b'_n) = 0$. The first few are (to 10 digits):

 $n$ $a_n$ $a'_n$ $b_n$ $b'_n$ 1 −2.338107410 −1.018792972 −1.173713223 −2.294439683 2 −4.087949444 −3.248197582 −3.271093303 −4.073155089 3 −5.520559828 −4.820099211 −4.830737842 −5.512395730 4 −6.786708090 −6.163307356 −6.169852128 −6.781294446 5 −7.944133587 −7.372177255 −7.376762079 −7.940178689

I have added the Airy functions to the real_roots example program in Arb. The root isolation code in real_roots is completely generic; it relies purely on being able to evaluate the object function and its derivatives in interval arithmetic. No information about the asymptotic distribution of the Airy function zeros is being exploited (the real_roots program also demonstrates computing zeros of the Riemann zeta function, among other things).

As an example, it takes 0.42 seconds to isolate the 6710 zeros of Ai on the interval $[-1000,0]$:

> build/examples/real_roots 4 -1000 0
interval: [-1000, 0]
maxdepth = 30, maxeval = 100000, maxfound = 100000, low_prec = 30
---------------------------------------------------------------
Found roots: 6710
Subintervals possibly containing undetected roots: 0
Function evaluations: 67630
cpu/wall(s): 0.422 0.422
virt/peak/res/peak(MB): 26.53 26.62 2.84 2.84

It takes 22 seconds to refine the same roots to 1000 digits each, using the generic interval-based Newton implementation in the real_roots program:

> build/examples/real_roots 4 -1000 0 -refine 1000
interval: [-1000, 0]
maxdepth = 30, maxeval = 100000, maxfound = 100000, low_prec = 30
refined root (0/6710):
[-999.91936797636384994814500357673698631708289035752812949732355246454007214238
25086529843391546979436196231893145318672911388387266290425955036381424104232098
21959382653054011888556159446303334635494058949724054670914786934157812832725621
48570812584692491527774337420208731102210790047229476074274853394924213976700895
97580436794894052812227037752689570656407403587710732355191345956498354320530151
18660106942295153080293923850567984960731493151090629784038685434639197165625890
85130653019088783348634739791224364373594066461909106531257454732410908834151192
38802875549281404703161420778764091123067337625555878759094759769005544736642007
89167465389486941290248512307222405921246839935100788138798415264483876537498881
25098099674593190356753322787295530107789755304296202511420183179820218581298845
86769916429662702945835883728795767839498403812110277990163911791399981306024793
52085495485976709757632171720364376730208389565085957359416676037020290396839781
305110544033095396544333692750290268350505130 +/- 4.50e-1000]

(... long output omitted ...)

refined root (6709/6710):
[-2.3381074104597670384891972524467354406385401456723878524838544372136680027002
83647782164041731329320284760093853265952775225466858359866744868898716819727540
97315267499111274806599964562835349155036724215460225304014264499417846393445344
44576009473858055993284003541978854868734370327947683736231269144363684562163216
95224896886771887967253644542964146651161756655217909281106701616013124010872087
51068015363540930435540173336518243684153688846153833781673263744772352166269178
98162900770617327677839962800890838040518659518893258577111583822210212170758191
40042838771579610361895347743266687702532274665250544694660076354855478498996553
85449531527883777571079976665872920752336809007511567307314992020073711012994084
30413874201048355826398350502612457374298884716015896813993360718225735302714533
73298042317302785618884411551002742408721103590746604387755833964377689014281692
08537738426486491923178234284354349366643196163933956066902105416207641584372042
297422983703788795834149300831159961531707775 +/- 3.12e-1002]

---------------------------------------------------------------
Found roots: 6710
Subintervals possibly containing undetected roots: 0
Function evaluations: 221960
cpu/wall(s): 22.593 22.891
virt/peak/res/peak(MB): 26.53 26.62 2.84 2.84

For comparison, mpmath takes 800 seconds to compute the same roots at low precision (by repeatedly calling mpmath.airyaizero), and an estimated 8000 seconds at 1000-digit precision. I tested Mathematica's AiryAiZero as well (on a different machine), and it takes 2.8 and 264 seconds respectively.

Returning to the Schrödinger equation, the $a_n$ are precisely the possible energy values of a quantum mechanical particle in a linear potential well, expressed in appropriate dimensionless units. (The $a'_n$ can also be energy values, depending on boundary conditions.) On a tangent to this, the late Richard Crandall wrote an interesting paper on so-called quantum zeta functions (On the quantum zeta function [PDF], J. Phys. A: Math. Gen. 29 (1996) 6795-6816). These are formal sums $$Z(s) = \sum_{k=1}^{\infty} \frac{1}{E_k^s}$$ where $E_k$ are the energy states of a fixed quantum system. The Airy zeta functions are $$Z(s) = \sum_{k=1}^{\infty} \frac{1}{a_k^s}, \quad z(s) = \sum_{k=1}^{\infty} \frac{1}{|a_k|^s}.$$ Remarkably, like the Riemann zeta function in the famous Basel problem, these functions have simple closed forms at the positive even integers $s = 2, 4, 6, \ldots$. For example, $$Z(2) = \frac{3^{5/3} \Gamma^4(2/3)}{4 \pi^2}.$$ Perhaps even more remarkably, Crandall conjectured special values for the analytic continuations of $z(s)$ and $Z(s)$, in particular $$z(1) \stackrel{?}{=} -\frac{\Gamma(2/3)}{3^{2/3} \Gamma(4/3)}.$$ This is, as far as I know, still an open conjecture!


text:
On the distance spectra of graphs

On the distance spectra of graphs

Ghodratollah Aalipour Department of Mathematics and Computer Sciences, Kharazmi University, 50 Taleghani St., Tehran, Iran and Department of Mathematical and Statistical Sciences, University of Colorado Denver, CO, USA (alipour.ghodratollah@gmail.com).    Aida Abiad Department of Quantitative Economics, Operations Research, Maastricht University, Maastricht, The Netherlands, (aidaabiad@gmail.com).    Zhanar Berikkyzy Department of Mathematics, Iowa State University, Ames, IA 50011, USA (zhanarb@iastate.edu, keheysse@iastate.edu, lhogben@iastate.edu, chlin@iastate.edu).    Jay Cummings Department of Mathematics, University of California, San Diego, La Jolla, CA 92037, USA (jjcummings@math.ucsd.edu, mtait@math.ucsd.edu).    Jessica De Silva Department of Mathematics, University of Nebraska-Lincoln, Lincoln, NE 68588, USA (jessica.desilva@huskers.unl.edu).    Wei Gao Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA (wgao2@gsu.edu).    Kristin Heysse1    Leslie Hogben1 American Institute of Mathematics, 600 E. Brokaw Road, San Jose, CA 95112, USA (hogben@aimath.org).    Franklin H.J. Kenter Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005, USA (franklin.h.kenter@rice.edu).    Jephian C.-H. Lin1    Michael Tait2
3footnotemark: 3
4footnotemark: 4
Abstract

The distance matrix of a graph is the matrix containing the pairwise distances between vertices. The distance eigenvalues of are the eigenvalues of its distance matrix and they form the distance spectrum of . We determine the distance spectra of halved cubes, double odd graphs, and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance matrices of lollipop and barbell graphs.

Keywords. distance matrix, eigenvalue, distance regular graph, Kneser graph, double odd graph, halved cube, Doob graph, lollipop graph, barbell graph, distance spectrum, strongly regular graph, optimistic graph, determinant, inertia, graph

AMS subject classifications. 05C12, 05C31, 05C50, 15A15, 15A18, 15B48, 15B57

1 Introduction

The distance matrix of a graph is the matrix indexed by the vertices of where is the distance between the vertices and , i.e., the length of a shortest path between and . Distance matrices were introduced in the study of a data communication problem in [16]. This problem involves finding appropriate addresses so that a message can move efficiently through a series of loops from its origin to its destination, choosing the best route at each switching point. Recently there has been renewed interest in the loop switching problem [13]. There has also been extensive work on distance spectra (eigenvalues of distance matrices); see [2] for a recent survey.

In [19], the authors classify the distance regular graphs having only one positive distance eigenvalue. Such graphs are directly related to a metric hierarchy for finite connected graphs (and more generally, for finite distance spaces, see [3, 11, 12, 18]), which makes these graphs particularly interesting. In Section 3 we find the distance spectra of Doob graphs, double odd graphs, and halved cubes, completing the determination of distance spectra of distance regular graphs that have one positive distance eigenvalue. In Section 2 we characterize strongly regular graphs having more positive than negative distance eigenvalues in terms of their parameters, generalizing results in [5], and apply this characterization to show several additional infinite families of strongly regular graphs have this property.

Section 4 contains examples of graphs with specific properties and a small number of distinct distance eigenvalues. Answering a question in [4], we provide a construction for a family of connected graphs with arbitrarily large diameter that have no more than 5 distinct distance eigenvalues but are not distance regular (Example 4.2). We exhibit a family of graphs with arbitrarily many distinct degrees but having exactly 5 distinct distance eigenvalues (Example 4.5). Finally, we give two lower bounds for the number of distinct distance eigenvalues of a graph. The first bound is for a tree, in terms of its diameter, and the second is for any graph in terms of the zero forcing number of its complement.

In Persi Diaconis’ talk on distance spectra at the “Connections in Discrete Mathematics: A celebration of the work of Ron Graham” [13], he suggested it would be worthwhile to study the distance matrix of a clique with a path adjoined (sometimes called a lollipop graph), and in Section 5 we determine determinants and inertias of these graphs, of barbell graphs, and of generalized barbell graphs (a family that includes both lollipops and barbells). The remainder of this introduction contains definitions and notation used throughout.

All graphs are connected, simple, undirected, and finite of order at least two. Let be a graph. The maximum distance between any two vertices in is called the diameter of and is denoted by . Two vertices are adjacent in the complement of , denoted by , if and only if they are nonadjacent in . Let denote the adjacency matrix of , that is, is the matrix indexed by the vertices of where if and is otherwise. The all ones matrix is denoted by and the all ones vector by . A graph is regular if every vertex has the same degree, say ; equivalently, ; observe that is the spectral radius of .

Since is a real symmetric matrix, its eigenvalues, called distance eigenvalues of , are all real. The spectrum of is denoted by where is the spectral radius, and is called the distance spectrum of the graph .

The inertia of a real symmetric matrix is the triple of integers , with the entries indicating the number of positive, zero, and negative eigenvalues, respectively (counting multiplicities). Note the order , while customary in spectral graph theory, is nonstandard in linear algebra, where it is more common to use . The spectrum of a matrix can be written as a multiset (with duplicates as needed), or as a list of distinct values with the exponents () in parentheses indicating multiplicity.

2 Strongly regular graphs

A -regular graph of order is strongly regular with parameters if every pair of adjacent vertices has common neighbors and every pair of distinct nonadjacent vertices has common neighbors. For a strongly regular graph with parameters , is equivalent to is copies of , so we assume and thus has diameter at most 2. There is a well known connection between the adjacency matrix of a graph of diameter at most and its distance matrix that was exploited in [5].

Remark 2.1.

A real symmetric matrix commutes with if and only if it has constant row sum. Suppose commutes with and is the constant row sum of , so and have a common eigenvector of . Since eigenvectors of real symmetric matrices corresponding to distinct eigenvalues are orthogonal, every eigenvector of for an eigenvalue other than is an eigenvector of for eigenvalue 0.

Now suppose is a graph that has diameter at most . Then . Now suppose in addition that is regular, so commutes with . Thus .

Let be a strongly regular graph with parameters . It is known that the (adjacency) eigenvalues of are of multiplicity , of multiplicity , and of multiplicity [15, Chapter 10].111These formulas do work for , but in that case . Thus the distance eigenvalues of are

 ρD:=2(n−1)−k of multiplicity 1 θD:=−12(λ−μ+√(λ−μ)2+4(k−μ))−2 of multiplicity mθ=12(n−1−2k+(n−1)(λ−μ)√(λ−μ)2+4(k−μ)) τD:=−12(λ−μ−√(λ−μ)2+4(k−μ))−2 of multiplicity mτ=12(n−1+2k+(n−1)(λ−μ)√(λ−μ)2+4(k−μ)).

For a derivation of these values using quotient matrices, see [4, p. 262].

2.1 Optimistic strongly regular graphs

A graph is optimistic if it has more positive than negative distance eigenvalues. Graham and Lovász raised the question of whether optimistic graphs exist (although they did not use the term). This question was answered positively by Azarija in [5], where the term ‘optimistic’ was introduced. A strongly regular graph is a conference graph if . In [5] it is shown that conference graphs of order at least 13 are optimistic and also that the strongly regular graphs with parameters are optimistic for . Additional examples of optimistic strongly regular graphs, such as the Hall–Janko graph with parameters (100, 36, 14, 12), and examples of optimistic graphs that are not strongly regular are also presented there.

Theorem 2.2.

Let be a strongly regular graph with parameters . The graph is optimistic if and only if and . That is, is optimistic if and only if

 λ<−4+μ+k2 and λ≥μ−2kn−1.
Proof.

Observe that . Thus is optimistic if and only if and . Simple algebra shows that is equivalent to :

 0 < −2−12(λ−μ−√(λ−μ)2+4(k−μ)) 4+λ−μ < √(λ−μ)2+4(k−μ).

There are two cases. First assume , so

 (λ−μ)2+8(λ−μ)+16 < (λ−μ)2+4(k−μ) λ < −4+μ+k2.

Now assume , or equivalently, . For any strongly regular graph, . Thus

 (λ−μ)+(λ−k) < −4 λ < −4+μ+k2.

It is well known [15, p. 222] (and easy to see) that

 mτ−mθ=2k+(n−1)(λ−μ)√(λ−μ)2+4(k−μ). (1)

The denominator is always positive, and thus if and only if . ∎

Corollary 2.3.

Whether or not a strongly regular graph is optimistic depends only on its parameters .

There are several additional families of strongly regular graphs for which the conditions in Theorem 2.2 hold.

Corollary 2.4.

A strongly regular graph with parameters is optimistic if and only if .

Proof.

By Theorem 2.2, implies , and is equivalent to

 0<−4+μ+k2−λ=12(k−μ−4).\qed

The family of symplectic graphs is defined using subspaces of a vector space over a field with a finite number of elements. Let be the field with elements and consider as vertices of the one dimensional subspaces of for ; let denote the subspace generated by . The alternate matrix of order over is the matrix with copies of . The vertices and are adjacent in if . See [15, Section 8.11] for and [23] for more general . It is known that the symplectic graph is a strongly regular graph with parameters

 (n,k,λ,μ)=(q2m−1q−1,q2m−1,q2m−2(q−1),q2m−2(q−1))

(see [15, Section 10.12] for or [23, Theorem 2.1] for more general ). The next result is immediate from Corollary 2.4.

Corollary 2.5.

The symplectic graphs are optimistic for every and except and .

There are additional families of optimistic strongly regular graphs with parameters . One example is the family on one type of nonisotropic points, which has parameters

 (3m(e+3m)2,3m−1(3m−e)2,3m−1(3m−1−e)2,3m−1(3m−1−e)2)

with and [7].

The more common definition of a conference graph is a strongly regular graph with ; this is equivalent to the definition given earlier as [15, Lemma 10.3.2].

Theorem 2.6.

Let be a strongly regular graph with parameters . Both and are optimistic if and only if is a conference graph and .

Proof.

The parameters of are . By Theorem 2.2 applied to and ,

 λ≥μ−2kn−1 (2)

and

 ¯λ ≥ ¯μ−2¯kn−1 n−2−2k+μ ≥ n−2k+λ−2(n−k−1)n−1 −2+2(n−k−1)n−1+μ ≥ λ μ−2kn−1 ≥ λ. (3)

By comparing (2) and (3), we see that , which by (1) implies . Thus is a conference graph. It is shown in [5] that conference graphs are optimistic if and only if the order is at least 13. ∎

2.2 Strongly regular graphs with one positive distance eigenvalue

Distance regular graphs (see Section 3 for the definition) having one positive distance eigenvalue were studied in [19]; strongly regular graphs are distance regular. Here we make some elementary observations about strongly regular graphs with one positive distance eigenvalue that will be used in Section 3.

Proposition 2.7.

Let be a strongly regular graph with parameters and (adjacency) eigenvalues , and . Then is a conference graph, , or . Thus has exactly one positive distance eigenvalue if and only if , , or .

Proof.

Assume has exactly one positive distance eigenvalue. Since and , . It is known that if a strongly regular graph is not a conference graph, then and are integers [15, Lemma 10.3.3]. If , then (this follows from [15, p. 219]), implying . Since , if and only if . As shown in [5] (see also Theorem 2.6), conference graphs of order at least 13 are optimistic and so have more than one positive eigenvalue. The conference graph on 5 vertices is , and the conference graph on 9 vertices has . Thus if and only if , , or . ∎

Observation 2.8.

There are several well known families of strongly regular graphs having , and thus having one positive distance eigenvalue. Examples of such graphs and their distance spectra include:

1. The cocktail party graphs are complete multipartite graphs on partite sets of order 2; is a strongly regular graph with parameters and has distance spectrum .

2. The line graph with parameters has distance spectrum
.

3. The line graph with parameters has distance spectrum
.

3 Distance regular graphs having one positive distance eigenvalue

Let be integers. The graph is called distance regular if for any choice of with , the number of vertices such that and is independent of the choice of and . Distance spectra of several families of distance regular graphs were determined in [4]. In this section we complete the determination of the distance spectra of all distance regular graphs having exactly one positive distance eigenvalue, as listed in [19, Theorem 1]. For individual graphs, it is simply a matter of computation, but for infinite families the determination is more challenging. The infinite families in [19, Theorem 1] are (with numbering from that paper):

1. cocktail party graphs ,

2. cycles (called polygons in [19]),

3. Hamming graphs ,

4. Doob graphs ,

5. Johnson graphs ,

6. double odd graphs , and

7. halved cubes .

First we summarize the known distance spectra of these infinite families. For a strongly regular graph, it is easy to determine the distance spectrum and we have listed the distance spectra of cocktail party graphs in Observation 2.8. The distance spectra of cycles are determined in [14], and in [4] are presented in the following form: For odd , , and for even the distance eigenvalues are and if is odd. Hamming graphs, whose distance spectra are determined in [17], are discussed in Section 3.1 (since they are used to construct Doob graphs). Johnson graphs, whose spectra are determined in [4], are discussed in Section 3.2 (because they are used to determine distance spectra of double odd graphs). The remaining families are defined and their distance spectra determined in Section 3.1 for Doob graphs, Section 3.2 for double odd graphs, and Section 3.3 for halved cubes. Thus all the infinite families in [19, Theorem 1] now have their distance spectra determined.

For completeness we list the distance spectra (some of which are known) for the individual graphs having exactly one positive distance eigenvalue; these are easily computed and we provide computational files in Sage [21]. Definitions of these graphs can be found in [2].

Proposition 3.1.

The graphs listed in [19, Theorem 1] that have one positive distance eigenvalue and are not in one of the infinite families, together with their distance spectra, are:

1. the Gosset graph; ,

2. the Schläfli graph; ,

3. the three Chang graphs (all the same spectra); ,

4. the icosahedral graph; ,

5. the Petersen graph; ,

6. the dodecahedral graph; .

A graph is transmission regular if (where is the constant row sum of ). Any distance regular graph is transmission regular. Here we present some tools for transmission regular graphs and matrices constructed from distance matrices of transmission regular graphs. We first define the cartesian product of two graphs: For graphs and define the graph to be the graph whose vertex set is the cartesian product and where two vertices and are adjacent if ( and ) or ( and ). The next theorem is stated for distance regular graphs in [17], but as noted in [4] the proof applies to transmission regular graphs.

Theorem 3.2.

[17, Theorem 2.1] Let and be transmission regular graphs with and . Then

 specD(G□G′)={n′ρ+nρ′}∪{n′θ2,…,n′θn}∪{nθ′2,…,nθ′n′}∪{0((n−1)(n′−1))}.
Lemma 3.3.

Let be an irreducible nonnegative symmetric matrix that commutes with . Suppose

 M=[aeD+beJ+ceIaoD+boJ+coIaoD+boJ+coIaeD+beJ+ceI],

, and (where is the row sum so ). Then

 spec(M) = {(ae+ao)ρ+(be+bo)n+(ce+co),(ae−ao)ρ+(be−bo)n+(ce−co)} ∪{(ae+ao)θi+(ce+co):i=2,…,n}∪{(ae−ao)θi+(ce−co):i=2,…,n},

where the union is a multiset union.

Proof.

Since commutes with , is an eigenvector of for eigenvalue . Thus is an eigenvector for and is an eigenvector for . Let be an eigenvector for (and assume is linearly independent). Since eigenvectors for distinct eigenvalues are orthogonal, , and thus . Define and . Then is an eigenvector of for eigenvalue and is an eigenvector of for eigenvalue . ∎

3.1 Hamming graphs and Doob graphs

A Doob graph is the cartesian product of copies of the Shrikhande graph and the Hamming graph . The Shrikhande graph is the graph where and . The distance spectrum is [21].

For and , the Hamming graph has vertex set consisting of all -tuples of elements taken from , with two vertices adjacent if and only if they differ in exactly one coordinate; is equal to with copies of . In [17] it is shown that the distance spectrum of the Hamming graph is

 specD(H(d,n))={dnd−1(n−1),0(nd−d(n−1)−1),(−nd−1)(d(n−1))}. (4)

Observe that the line graph is the Hamming graph .

Theorem 3.4.

The distance spectrum of the Doob graph is

 {3(2m+d)42m+d−1,0(42m+d−6m−3d−1),(−42m+d−1)(6m+3d)}.
Proof.

Let be the cartesian product of copies of the Shrikhande graph. Then . First we show that

 specD(Sm)={6m42m−1,0(16m−6m−1),(−42m−1)(6m)} (5)

by induction on . It is clear that the result holds for . Assume the result holds for . Then by induction hypothesis, . By Theorem 3.2, we have

 specD(Sm) = specD(Sm−1□S) = {16⋅6(m−1)42m−3+16m−1⋅24} ∪ {(16⋅0)(16m−1−6m+5),(−16⋅42m−3)(6m−6)} ∪ {(16m−1⋅0)(9),(−16m−1⋅4)(6)}∪{0(16m−1−1)(16−1)} = {6m42m−1,0(16m−6m−1),(−42m−1)(6m)}.

From (4), . Then by (5) and Theorem 3.2, we have

 specD(D(m,d)) = specD(Sm□H(d,4)) = {4d6m42m−1+16m3d4d−1}∪{(4d⋅0)(16m−6m−1),(−4d42m−1)(6m)} ∪{(16m⋅0)(4d−3d−1),(−16m4d−1)(3d)}∪{0(16m−1)(4d−1)} = {3(2m+d)42m+d−1,0(42m+d−6m−3d−1),(−42m+d−1)(6m+3d)}.\qed

3.2 Johnson, Kneser, and double odd graphs

Before defining Johnson graphs, we consider a more general family that includes both Johnson and Kneser graphs. For fixed and , let and denote the collection of all -subsets of . For fixed , the graph is the graph defined on vertex set such that two vertices and are adjacent if and only if .222Note the definition of this family of graphs varies with the source. Here we follow [6], whereas in [15] the graph defined by , and is what is here denoted by . The Johnson graphs are the graphs , and they are distance regular. Observe that the line graph is the Johnson graph . The distance spectrum of Johnson graphs are determined in [4, Theorem 3.6]:

 specD(J(n,r))=⎧⎨⎩s(n,r),0((nr)−n),(−s(n,r)n−1)(n−1)⎫⎬⎭ (6)

where .

Although they do not necessarily have one distance positive eigenvalue and are not all distance regular, Kneser graphs can be used to construct double odd graphs. The Kneser graph is the graph on the vertex set such that two vertices and are adjacent if and only if . Of particular interest are the odd graphs .

A double odd graph is a graph whose vertices are -element or -element subsets of , where two vertices and are adjacent if and only if or , as subsets. Double odd graphs can also be constructed as tensor products of odd graphs. We first define the tensor product of two graphs: For graphs and define the graph to be the graph whose vertex set is the cartesian product and where two vertices and are adjacent if and . To see that , observe that has as vertices two copies of the vertices of , call them and . Then there are no edges just between the vertices of the form , no edges just between the , and if and only if . Equivalently, if and only if . We will work with the representation of as .

Remark 3.5.

Let be a graph that is not bipartite. Then is a connected bipartite graph and has the form , where and are nonnegative symmetric matrices with the entries of even and those of odd; all of these statements are obvious except the symmetry of . Observe that is the matrix whose -entry is the shortest even distance between vertices and in , and is the matrix whose -entry is the shortest odd distance between vertices and in .

It is known [24] that the distance between two vertices and in is given by the formula

which for the odd graph is

 dO(S,T)=min{2(r−|S∩T|),2|S∩T|+1}. (7)

The distance between two vertices and in the Johnson graph is given by the formula

 dJ(n,r)(S,T)=12|SΔT|=r−|S∩T|, (8)

where is the symmetric difference. Let .

Proposition 3.6.

In , if and only if . Furthermore, for , .

Proof.

The first statement follows from equations (7) and (8) (it also follows from the definition). To prove the second part, let be a path of minimum even length between and , then is a path of length in the Johnson graph by the first statement. Conversely any path of the length in the Johnson graph between and provides a path of length between and in the odd graph (note that the new vertices are pairwise distinct). This implies the second statement. ∎

For , .

Proof.

Let and be two vertices of the odd graph . Let be an -subset of containing . Thus has the maximum size among all -subsets of . Now the minimum odd distance between and is one more than the minimum even distance between and a neighbor of in the Kneser graph . By Proposition 3.6, this is , where is a neighbor of in that maximizes . It suffices to set . This implies that the minimum odd distance between and is

 1+2dJ(S,˜T)=1+2(r−|S∩˜T|)=2r+1−2|S∩˜T|=2r+1−2(|S∖T|)
 =2r+1−2(|S|−|S∩T|)=2r+1−2(r−|S∩T|)=2r+1−2dJ(S,T).\qed
Theorem 3.8.

Let be the distance matrix of the Johnson graph , let be the all ones matrix of order , and let . The distance matrix of the double odd graph is

 [DeDoDoDe]=[2D(2r+1)J−2D(2r+1)J−2D2D]

and its distance spectrum is

Proof.

The first statement follows from Remark 3.5 and Propositions 3.6 and 3.7. From Equation (6), where . Since is distance regular, it is transmission regular, that is, commutes with . Then Lemma 3.3 establishes the result. ∎

We now return to arbitrary Kneser graphs and determine their distance spectra. Let be the distance matrix of . Let be the identity matrix of order and the adjacency matrix of for . It follows that

 D=r∑i=0f(i)Ai, where f(i)=min{2⌈in−2r⌉,2⌈r−in−2r⌉+1}.

It is known that forms an association scheme called the Johnson scheme and the following properties come from the Corollary to Theorem 2.9 and from Theorem 2.10 in [6]. For more information about association schemes, see, e.g., Section 2.3 in [6].

Theorem 3.9.

[6] The matrices form a commuting family and are simultaneously diagonalizable. There are subspaces such that

• the whole space is the direct sum of ;

• for each ,

 pi(j)=j∑t=0(−1)t(jt)(r−ji−t)(n−r−ji−t)

is an eigenvalue with multiplicity whose eigenspace is .

The value


text:
A nonlinear relativistic approach to mathematical representation of vacuum electromagnetism based on extended Lie derivative    [PDF]

Stoil Donev, Maria Tashkova
This paper presents an alternative {\it relativistic nonlinear} approach to the vacuum case of classical electrodynamics. Our view is based on the understanding that the corresponding differential equations should be dynamical in nature. So, they must represent local energy-momentum balance relations. Formally, the new equations are in terms of appropriately extended Lie derivative of $\mathbb{R}^2$-valued differential 2-form along a $\mathbb{R}^2$-valued 2-vector on Minkowski space-time.
View original: http://arxiv.org/abs/1305.3451